|
%I M1639 N0641 #163 Feb 28 2024 08:09:28
%S 1,1,2,6,19,63,216,760,2725,9910,36446,135268,505861,1903890,7204874,
%T 27394666,104592937,400795844,1540820542,5940738676,22964779660,
%U 88983512783,345532572678,1344372335524,5239988770268,20457802016011,79992676367108,313224032098244,1228088671826973
%N Number of fixed polyominoes with n cells.
%C Number of rookwise connected patterns of n square cells.
%C N. Madras proved in 1999 the existence of lim_{n->oo} a(n+1)/a(n), which is the real limit growth rate of the number of polyominoes; and hence, this limit is equal to lim_{n->oo} a(n)^{1/n}, the well-known Klarner's constant. The currently best-known lower and upper bounds on this constant are 3.9801 (Barequet et al., 2006) and 4.6496 (Klarner and Rivest, 1973), respectively. But see also Knuth (2014).
%D Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 378-382.
%D J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 229.
%D A. J. Guttmann, ed., Polygons, Polyominoes and Polycubes, Springer, 2009, p. 478. (Table 16.10 has 56 terms of this sequence.)
%D I. Jensen. Counting polyominoes: a parallel implementation for cluster computing. LNCS 2659 (2003) 203-212, ICCS 2003
%D W. F. Lunnon, Counting polyominoes, pp. 347-372 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
%D W. F. Lunnon, Counting hexagonal and triangular polyominoes, pp. 87-100 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Gill Barequet and Gil Ben-Shachar, <a href="/A001168/b001168.txt">Table of n, a(n) for n = 0..70</a>, a(0)..a(56) from Iwan Jensen.
%H Michael H. Albert, Christian Bean, Anders Claesson, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, <a href="https://arxiv.org/abs/2202.07715">Combinatorial Exploration: An algorithmic framework for enumeration</a>, arXiv:2202.07715 [math.CO], 2022.
%H G. Barequet and R. Barequet, <a href="https://doi.org/10.1016/j.endm.2015.06.025">An Improved Upper Bound on the Growth Constant of Polyominoes</a>, Electronic Notes in Discrete Math., 2015.
%H Gill Barequet and Gil Ben-Shachar, <a href="https://doi.org/10.1137/1.9781611977929.10">Counting Polyominoes, Revisited</a>, Proc. Symp. Algor. Eng. Exp. (ALENEX 2024), 133-143.
%H Gill Barequet, Gil Ben-Shachar, and Martha Carolina Osegueda, <a href="http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_23.pdf">Applications of Concatenation Arguments to Polyominoes and Polycubes</a>, EuroCG '20, 36th European Workshop on Computational Geometry, (Würzburg, Germany, 16-18 March 2020).
%H G. Barequet, M. Moffie, A. Ribo, and G. Rote, <a href="http://www.emis.de/journals/INTEGERS/papers/g22/g22.Abstract.html">Counting polyominoes on twisted cylinders</a>, Integers 6 (2006), A22, 37 pp. (electronic).
%H Gill Barequet and M. Shalah, <a href="http://www.eurocg2016.usi.ch/sites/default/files/paper_19.pdf">Improved Bounds on the Growth Constant of Polyiamonds</a>, 32nd European Workshop on Computational Geometry, 2016.
%H Gill Barequet, Solomon W. Golomb, and David A. Klarner, Polyominoes. (This is a revision, by G. Barequet, of the chapter of the same title originally written by the late D. A. Klarner for the first edition, and revised by the late S. W. Golomb for the second edition.) <a href="http://www.csun.edu/~ctoth/Handbook/chap14.pdf">Preprint</a>, 2016.
%H Vuong Bui, <a href="https://arxiv.org/abs/2211.14909">An asymptotic lower bound on the number of polyominoes</a>, arXiv:2211.14909 [math.CO], 2022-2023. See footnote 4 for a(69) = 4619282047583828929546825973053580643926 and a(70) = 18500792645885711270652890811942343400814, attributed to Gill Barequet and Gil Ben-Shachar.
%H Stirling Chow and Frank Ruskey, <a href="https://doi.org/10.1016/j.disc.2007.11.038">Gray codes for column-convex polyominoes and a new class of distributive lattices</a>, Discrete Mathematics, 309 (2009), 5284-5297.
%H A. R. Conway and A. J. Guttmann, <a href="http://dx.doi.org/10.1088/0305-4470/28/4/015">On two-dimensional percolation</a>, J. Phys. A: Math. Gen. 28(1995) 891-904.
%H Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/rndprc/anml.html">Klarner's Lattice Animal Constant</a> [Broken link]
%H Steven R. Finch, <a href="http://web.archive.org/web/20010603070928/http://www.mathsoft.com/asolve/constant/rndprc/anml.html">Klarner's Lattice Animal Constant</a> [From the Wayback machine]
%H J. Fortier, A. Goupil, J. Lortie and J. Tremblay, <a href="http://dx.doi.org/10.1016/j.tcs.2012.02.032">Exhaustive generation of gominoes</a>, Theoretical Computer Science, 2012. - _N. J. A. Sloane_, Sep 20 2012
%H I. Jensen, <a href="http://arxiv.org/abs/cond-mat/0007239">Enumerations of lattice animals and trees</a>, arXiv:cond-mat/0007239.
%H I. Jensen, <a href="https://doi.org/10.1023/A:1004855020556">Enumerations of lattice animals and trees</a>, J. Stat. Phys. 103 (3-4) (2001) 865-881, Table II.
%H I. Jensen, <a href="https://web.archive.org/web/20160101130205/http://www.ms.unimelb.edu.au/~iwan/">Home page</a>
%H I. Jensen, <a href="https://web.archive.org/web/20151222163324/http://www.ms.unimelb.edu.au/~iwan/saw/SAW_ser.html">More terms</a> [Go to series, animals, number of animals]
%H I. Jensen, <a href="/A001168/a001168.pdf">More terms</a> [pdf file of lost web link]
%H I. Jensen and A. J. Guttmann, <a href="http://dx.doi.org/10.1088/0305-4470/33/29/102">Statistics of lattice animals (polyominoes) and polygons</a>, J. Phys. A 33, L257-L263 (2000).
%H D. A. Klarner and R. L. Rivest, <a href="http://dx.doi.org/10.4153/CJM-1973-060-4">A procedure for improving the upper bound for the number of n-ominoes</a>, Canadian J. of Mathematics, 25 (1973), 585-602.
%H D. E. Knuth, <a href="https://www-cs-faculty.stanford.edu/~knuth/programs/polynum.w">Program</a>
%H D. E. Knuth, <a href="/A001168/a001168.txt">First 47 terms</a>
%H D. E. Knuth, <a href="https://www-cs-faculty.stanford.edu/~knuth/papers/flaj2014.pdf">Problems That Philippe Would Have Loved</a>, Paris 2014.
%H C. Lesieur and L. Vuillon, <a href="http://dx.doi.org/10.5772/58577">From Tilings to Fibers - Bio-mathematical Aspects of Fold Plasticity</a>, Chapter 13 (pages 395-422) of "Oligomerization of Chemical and Biological Compounds", book edited by Claire Lesieur, ISBN 978-953-51-1617-2, 2014.
%H N. Madras, <a href="http://arxiv.org/abs/math/9902161">A pattern theorem for lattice clusters</a>, arXiv:math/9902161 [math.PR], 1999; Annals of Combinatorics, 3 (1999), 357-384.
%H Toufik Mansour and Armend Sh. Shabani, <a href="http://www.dmlett.com/archive/DML19_v2_p.65_94.pdf">Enumerations on bargraphs</a>, Discrete Math. Lett. (2019) Vol. 2, 65-94.
%H Tomás Oliveira e Silva, <a href="http://sweet.ua.pt/tos/animals.html">Enumeration of polyominoes</a>
%H Jaime Rangel-Mondragón, <a href="https://web.archive.org/web/20190411024906/http://www.mathematica-journal.com/issue/v9i3/polyominoes.html">Polyominoes and Related Families</a>, The Mathematica Journal, Volume 9, Issue 3.
%H D. H. Redelmeier, <a href="http://dx.doi.org/10.1016/0012-365X(81)90237-5">Counting polyominoes: yet another attack</a>, Discrete Math., 36 (1981), 191-203.
%H M. F. Sykes and M. Glen, <a href="https://doi.org/10.1088/0305-4470/9/1/014">Percolation processes in two dimensions. I. Low-density series expansions</a>, J. Phys. A 9 (1) (1987) 87.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Polyomino.html">Polyomino</a>
%H <a href="/index/Pol#polyominoes">Index entries for sequences related to polyominoes</a>
%F For asymptotics, see Knuth (2014).
%F a(n) = 8*A006749(n) + 4*A006746(n) + 4*A006748(n) + 4*A006747(n) + 2*A056877(n) + 2*A056878(n) + 2*A144553(n) + A142886(n); the number of fixed polyominoes is calculatable according to multiples of the numbers of the various symmetries of the polyomino. - _John Mason_, Sep 06 2017
%e a(0) = 1 as there is 1 empty polyomino with #cells = 0. - _Fred Lunnon_, Jun 24 2020
%t See Jaime Rangel-Mondragón's article.
%Y Cf. A000105, A000988, A006746, A056877, A006748, A056878, A006747, A006749, A142886, A144553, row sums of A308359, A210986 (bisection), A210987 (bisection).
%Y A006762 is another version.
%Y Excluding a(0), 8th and 9th row of A366767.
%K nonn,nice
%O 0,3
%A _N. J. A. Sloane_
%E Extended to n=28 by Tomás Oliveira e Silva
%E Extended to n=46 by Iwan Jensen
%E Verified (and one more term found) by _Don Knuth_, Jan 09 2001
%E Richard C. Schroeppel communicated Jensen's calculation of the first 56 terms, Feb 21 2005
%E Gill Barequet commented on Madras's proof from 1999 of the limit growth rate of this sequence, and provided references to the currently best-known bounds on it, May 24 2011
%E Incorrect Mathematica program removed by _Jean-François Alcover_, Mar 24 2015
%E a(0) = 1 added by _N. J. A. Sloane_, Jun 24 2020
| 