The Number of Snakes in a Box

Abstract

Within the class of polyominoes we work on the enumeration of two subfamilies of the family of snake polyominoes: stairs and snakes of height 2. We consider them from a graph theoretical perspective. In the process of enumeration of these graphs, we use classical ideas, as symmetries, and a new approach that connects these snakes with the partitions of integers.

Keywords

• Partition,Polyomino,Snake

References

1. [1] D. Battaglino, A. Frosini, V. Guerrini, Binary pictures with excluded patters, Discrete Geometry for Computer Imagery, 18th IAPR International Conference, (2014), 25–38.
2. [2] S. W. Golomb, (2nd ed.), Polyominoes: Ouzzles, Patterns, Problems, and Packings, Princeton University Press, Princeton, MA, 1996.
3. [3] A. Goupil, M.-E. Pellerin, J. de Wouters d’Oplinter, Partially directed snake polyominoes, Discrete Appl. Math., 236 (2018), 223–234.
4. [4] E. Pegg Jr., https://oeis.org/A002013, 2009.
5. [5] C. Barrientos, Graceful labelings of cyclic snakes, Ars Combin., 60 (2001), 85–96.
6. [6] C. Barrientos, S. Minion, Snakes: from graceful to harmonious, Bull. Inst. Combin. Appl., 79 (2017), 95–107.
7. [7] N. J. A. Sloane, R. K. Guy, https://oeis.org/A005418, 2012.
8. [8] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris, (1967), 349–355.

9. [9] C. Barrientos, S. Minion, On the number of a-labeled graphs, Discuss. Math. Graph Theory, 38 (2018), 177–188.
10. [10] J. A. Gallian, A dynamic survey of graph labelings, Electron. J. Combin., (2017), #DS6.
11. [11] E. Deutsch, https://oeis.org/A102547, 2010.
12. [12] N. J. A. Sloane, https://oeis.org/A226916, 2013.
13. [13] G. McGarvey,, https://oeis.org/A102543, 2005.
14. [14] N. J .A. Sloane, https://oeis.org/A078012, 2002.