

A001168


Number of fixed polyominoes with n cells.
(Formerly M1639 N0641)


58



1, 1, 2, 6, 19, 63, 216, 760, 2725, 9910, 36446, 135268, 505861, 1903890, 7204874, 27394666, 104592937, 400795844, 1540820542, 5940738676, 22964779660, 88983512783, 345532572678, 1344372335524, 5239988770268, 20457802016011, 79992676367108, 313224032098244, 1228088671826973
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Number of rookwise connected patterns of n square cells.
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 wellknown Klarner's constant. The currently bestknown 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).


REFERENCES

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 378382.
J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 229.
A. J. Guttmann, ed., Polygons, Polyominoes and Polycubes, Springer, 2009, p. 478. (Table 16.10 has 56 terms of this sequence.)
I. Jensen. Counting polyominoes: a parallel implementation for cluster computing. LNCS 2659 (2003) 203212, ICCS 2003
W. F. Lunnon, Counting polyominoes, pp. 347372 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
W. F. Lunnon, Counting hexagonal and triangular polyominoes, pp. 87100 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

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.) Preprint, 2016.
Vuong Bui, An asymptotic lower bound on the number of polyominoes, arXiv:2211.14909 [math.CO], 20222023. See footnote 4 for a(69) = 4619282047583828929546825973053580643926 and a(70) = 18500792645885711270652890811942343400814, attributed to Gill Barequet and Gil BenShachar.
I. Jensen, More terms [Go to series, animals, number of animals]
Eric Weisstein's World of Mathematics, Polyomino


FORMULA

For asymptotics, see Knuth (2014).


EXAMPLE

a(0) = 1 as there is 1 empty polyomino with #cells = 0.  Fred Lunnon, Jun 24 2020


MATHEMATICA

See Jaime RangelMondragón's article.


CROSSREFS

Cf. A000105, A000988, A006746, A056877, A006748, A056878, A006747, A006749, A142886, A144553, row sums of A308359, A210986 (bisection), A210987 (bisection).
Excluding a(0), 8th and 9th row of A366767.


KEYWORD

nonn,nice


AUTHOR



EXTENSIONS

Extended to n=28 by Tomás Oliveira e Silva
Extended to n=46 by Iwan Jensen
Verified (and one more term found) by Don Knuth, Jan 09 2001
Richard C. Schroeppel communicated Jensen's calculation of the first 56 terms, Feb 21 2005
Gill Barequet commented on Madras's proof from 1999 of the limit growth rate of this sequence, and provided references to the currently bestknown bounds on it, May 24 2011


STATUS

approved



