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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001168 Number of fixed polyominoes with n cells.
(Formerly M1639 N0641)
28
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

1,2

COMMENTS

Number of rookwise connected patterns of n square cells.

N. Madras proved in 1999 the existence of the lim_{n \to \infty} 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 \to \infty} 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).

REFERENCES

G. Barequet, M. Moffie, A. Ribo, and G. Rote, Counting polyominoes on twisted cylinders, Integers (electronic journal, 6 (2006), A22, 37 pp.

Stirling Chow and Frank Ruskey, Gray codes for column-convex polyominoes and a new class of distributive lattices, Discrete Mathematics, 309 (2009), 5284-5297. [From N. J. A. Sloane, Sep 15 2009]

A. R. Conway and A. J. Guttmann, On two-dimensional percolation, J. Phys. A: Math. Gen. 28(1995) 891-904.

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 378-382.

J. Fortier, A. Goupil, J. Lortie and J. Tremblay, Exhaustive generation of gominoes, Theoretical Computer Science, 2012; http://dx.doi.org/10.1016/j.tcs.2012.02.032. - From N. J. A. Sloane, Sep 20 2012

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.) [From Robert A. Russell, Nov 05 2010]

I. Jensen and A. J. Guttmann, Statistics of lattice animals (polyominoes) and polygons. J. Phys. A 33, L257-L263 (2000).

D. A. Klarner and R. L. Rivest, A procedure for improving the upper bound for the number of n-ominoes, Canadian J. of Mathematics, 25 (1973), 585-602.

C. Lesieur, L. Vuillon, From Tilings to Fibers - Bio-mathematical Aspects of Fold Plasticity, Chapter 13 (pages 395-422) of "Oligomerization of Chemical and Biological Compounds" (?), 2014; http://dx.doi.org/10.5772/58577

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.

W. F. Lunnon, Counting hexagonal and triangular polyominoes, pp. 87-100 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.

N. Madras, A pattern theorem for lattice clusters, Annals of Combinatorics, 3 (1999), 357-384.

D. H. Redelmeier, Counting polyominoes: yet another attack, Discrete Math., 36 (1981), 191-203.

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 = 1..56

S. R. Finch, Klarner's Lattice Animal Constant

I. Jensen, Enumerations of lattice animals and trees, arXiv:cond-mat/0007239.

I. Jensen, Home page

I. Jensen, More terms

D. E. Knuth, Program

D. E. Knuth, First 47 terms

D. E. Knuth, Problems That Philippe Would Have Loved, Paris 2014.

Tomas Oliveira e Silva, Enumeration of polyominoes

Eric Weisstein's World of Mathematics, Polyomino

FORMULA

For asymptotics, see Knuth (2014).

MATHEMATICA

(* This program is not convenient for more than 12 terms *) cyclic[p_] := Module[{i = p, ans = {p}}, While[(i = rot[i]) != p, AppendTo[ans, i]]; ans]; dihedral[p_] := Flatten[({#1, ref[#1]} & ) /@ cyclic[p], 1]; canonical[p_] := Union[(#1 - (I*Min[Im[p]] + Min[Re[p]]) & ) /@ p]; allPieces[p_] := Union[canonical /@ dihedral[p]]; polyominoes[1] := {{0}}; polyominoes[n_] := polyominoes[n] = Module[{f, fig, ans = {}}, fig = ((f = #1; ({f, #1 + 1, f, #1 + I, f, #1 - 1, f, #1 - I} & ) /@ f) & ) /@ polyominoes[n - 1]; fig = Partition[Flatten[fig], n]; f = Select[Union[canonical /@ fig], Length[#1] == n & ]; While[f != {}, ans = {ans, First[f]}; f = Complement[f, allPieces[First[f]]]]; Partition[Flatten[ans], n]]; a[n_] := a[n] = Length[polyominoes[n]]; Table[Print[{n, a[n]}]; a[n], {n, 1, 12}] (* Jean-François Alcover, Jan 15 2013, copied from Jaime Rangel-Mondragón's article *)

CROSSREFS

Cf. A000105, A006746, A056877, A006748, A056878, A006747, A006749, A006884, A006885, A006877, A006878, A033492.

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 Tomas Oliveira e Silva. Extended to n=46 by Iwan Jensen. Verified (and one more term found) by D. E. Knuth, Jan 09 2001.

Richard 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 best-known bounds on it, May 24, 2011.

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified December 19 08:21 EST 2014. Contains 252186 sequences.