login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001168 Number of fixed polyominoes with n cells.
(Formerly M1639 N0641)
38

%I M1639 N0641

%S 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 I. Jensen, <a href="/A001168/b001168.txt">Table of n, a(n) for n = 1..56</a>

%H G. Barequet, 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 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, 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 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="http://www-cs-faculty.stanford.edu/~knuth/programs.html#polyominoes">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, 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 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="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, M. Glen, <a href="https://iopscience.iop.org/article/10.1088/0305-4470/9/1/014/pdf">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>

%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

%t See Jaime Rangel-Mondragón's article.

%Y Cf. A000105, A006746, A056877, A006748, A056878, A006747, A006749, A006884, A006885, A006877, A006878, A033492, row sums of A308359.

%Y A006762 is another version.

%K nonn,nice

%O 1,2

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 25 16:17 EDT 2019. Contains 326324 sequences. (Running on oeis4.)