

A001168


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


42



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

I. Jensen, Table of n, a(n) for n = 0..56
G. Barequet, R. Barequet, An Improved Upper Bound on the Growth Constant of Polyominoes, Electronic Notes in Discrete Math., 2015.
Gill Barequet, Gil BenShachar, Martha Carolina Osegueda, Applications of Concatenation Arguments to Polyominoes and Polycubes, EuroCG '20, 36th European Workshop on Computational Geometry, (Würzburg, Germany, 1618 March 2020).
G. Barequet, M. Moffie, A. Ribo, and G. Rote, Counting polyominoes on twisted cylinders, Integers 6 (2006), A22, 37 pp. (electronic).
Gill Barequet, M. Shalah, Improved Bounds on the Growth Constant of Polyiamonds, 32nd European Workshop on Computational Geometry, 2016.
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.
Stirling Chow and Frank Ruskey, Gray codes for columnconvex polyominoes and a new class of distributive lattices, Discrete Mathematics, 309 (2009), 52845297.
A. R. Conway and A. J. Guttmann, On twodimensional percolation, J. Phys. A: Math. Gen. 28(1995) 891904.
Steven R. Finch, Klarner's Lattice Animal Constant [Broken link]
Steven R. Finch, Klarner's Lattice Animal Constant [From the Wayback machine]
J. Fortier, A. Goupil, J. Lortie and J. Tremblay, Exhaustive generation of gominoes, Theoretical Computer Science, 2012.  N. J. A. Sloane, Sep 20 2012
I. Jensen, Enumerations of lattice animals and trees, arXiv:condmat/0007239.
I. Jensen, Enumerations of lattice animals and trees, J. Stat. Phys. 103 (34) (2001) 865881, Table II.
I. Jensen, Home page
I. Jensen, More terms [Go to series, animals, number of animals]
I. Jensen, More terms [pdf file of lost web link]
I. Jensen and A. J. Guttmann, Statistics of lattice animals (polyominoes) and polygons, J. Phys. A 33, L257L263 (2000).
D. A. Klarner and R. L. Rivest, A procedure for improving the upper bound for the number of nominoes, Canadian J. of Mathematics, 25 (1973), 585602.
D. E. Knuth, Program
D. E. Knuth, First 47 terms
D. E. Knuth, Problems That Philippe Would Have Loved, Paris 2014.
C. Lesieur, L. Vuillon, From Tilings to Fibers  Biomathematical Aspects of Fold Plasticity, Chapter 13 (pages 395422) of "Oligomerization of Chemical and Biological Compounds", book edited by Claire Lesieur, ISBN 9789535116172, 2014.
N. Madras, A pattern theorem for lattice clusters, arXiv:math/9902161 [math.PR], 1999; Annals of Combinatorics, 3 (1999), 357384.
Toufik Mansour, Armend Sh. Shabani, Enumerations on bargraphs, Discrete Math. Lett. (2019) Vol. 2, 6594.
Tomás Oliveira e Silva, Enumeration of polyominoes
Jaime RangelMondragón, Polyominoes and Related Families, The Mathematica Journal, Volume 9, Issue 3.
D. H. Redelmeier, Counting polyominoes: yet another attack, Discrete Math., 36 (1981), 191203.
M. F. Sykes, M. Glen, Percolation processes in two dimensions. I. Lowdensity series expansions, J. Phys. A 9 (1) (1987) 87.
Eric Weisstein's World of Mathematics, Polyomino
Index entries for sequences related to polyominoes


FORMULA

For asymptotics, see Knuth (2014).
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


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, A006884, A006885, A006877, A006878, A033492, row sums of A308359, A210986 (bisection), A210987 (bisection).
A006762 is another version.
Sequence in context: A057409 A141771 A001170 * A193111 A119255 A071969
Adjacent sequences: A001165 A001166 A001167 * A001169 A001170 A001171


KEYWORD

nonn,nice


AUTHOR

N. J. A. Sloane


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
Incorrect Mathematica program removed by JeanFrançois Alcover, Mar 24 2015
a(0) = 1 added by N. J. A. Sloane, Jun 24 2020


STATUS

approved



