|
| |
|
|
A000105
|
|
Number of free polyominoes (or square animals) with n cells.
(Formerly M1425 N0561)
|
|
70
|
|
|
|
1, 1, 1, 2, 5, 12, 35, 108, 369, 1285, 4655, 17073, 63600, 238591, 901971, 3426576, 13079255, 50107909, 192622052, 742624232, 2870671950, 11123060678, 43191857688, 168047007728, 654999700403, 2557227044764, 9999088822075, 39153010938487, 153511100594603
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
a(n) + A030228(n) = A000988(n) because the number of free polyominoes plus the number of polyominoes lacking bilateral symmetry equals the number of one-sided polyominoes. - Graeme McRae, Jan 05 2006
The possible symmetry groups of a (nonempty) polyomino are the 10 subgroups of the dihedral group D_8 of order 8: D_8, 1, Z_2 (five times), Z_4, (Z_2)^2 (twice). - Benoit Jubin, Dec 30 2008
Names for first few polyominoes: "monomino", "domino", "tromino", "tetromino", "pentomino", "hexomino", "heptomino", "octomino", "enneomino", "decomino", "hendecomino", "dodecomino", ...
lim_{n->oo} a(n)^(1/n) = mu with 3.98 < mu < 4.64 (quoted by Castiglione et al., with a reference to Barequet et al., 2006, for the lower bound). Upper bound is due to Klarner and Rivest, 1973. By Madras, 1999, it is now known that this limit, also known as Klarner's constant, is equal to the limit growth rate lim_{n->oo} a(n+1)/a(n).
|
|
|
REFERENCES
|
Barequet, Gill; Moffie, Micha; Ribo, Ares; and Rote, Guenter, Counting polyominoes on twisted cylinders. Integers 6 (2006), A22, 37 pp. (electronic).
G. Castiglione, A. Frosini, E. Munarini, A. Restivo and S. Rinaldi, Combinatorial aspects of L-convex polyominoes, to appear in European Journal of Combinatorics, 2007.
A. R. Conway and A. J. Guttmann, On two-dimensional percolation, J. Phys. A: Math. Gen. 28(1995) 891-904.
S. W. Golomb, Polyominoes, Appendix D, p. 152; Princeton Univ. Pr. NJ 1994
J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 229.
I. Jensen and A. J. Guttmann, Statistics of lattice animals (polyominoes) and polygons, Journal of Physics A: Mathematical and General, vol. 33, pp. 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.
D. A. Klarner, The Mathematical Gardner, p. 252 Wadsworth Int. CA 1981
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.
S. Mertens, Lattice animals: a fast enumeration algorithm and new perimeter polynomials, J. Statistical Physics, vol. 58, no. 5/6, pp. 1095-1108, Mar. 1990.
S. Mertens, Counting lattice animals: a parallel attack, Journal of Statistical Physics, vol. 66, no. 1/2, pp. 669-678, 1992.
Ed Pegg, Jr., Polyform puzzles, in Tribute to a Mathemagician, Peters, 2005, pp. 119-125.
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
R. C. Read, Some applications of computers in graph theory, in L. W. Beineke and R. J. Wilson, editors, Selected Topics in Graph Theory, Academic Press, NY, 1978, pp. 417-444.
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
|
Toshihiro Shirakawa, Table of n, a(n) for n=0 ..45
Z. Abel, E. Demaine, M. Demaine, H. Matsui and G. Rote, Common Developments of Several Different Orthogonal Boxes.
I. Jensen, Enumerations of lattice animals and trees, arXiv:cond-mat/0007239.
K. S. Brown, Polyomino Enumerations
A. Clarke, Polyominoes
M. Keller, Counting polyforms.
Joseph Myers, Polyomino tiling
Tomas Oliveira e Silva, Animal enumerations on regular tilings in Spherical, Euclidean and Hyperbolic 2-dimensional spaces
Tomas Oliveira e Silva, Animal enumerations on the {4,4} Euclidean tiling [The enumeration to order 28]
Ed Pegg, Jr., Illustrations of polyforms
Jaime Rangel-Mondragón, Polyominoes and Related Families.
D. H. Redelmeier, Table 3 of Counting polyominoes...
Eric Weisstein's World of Mathematics, Polyomino
Wikipedia, The 369 octominoes
L. Zucca, Pentominoes
L. Zucca, The 12 pentominoes
|
|
|
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
|
Sequences classifying polyominoes by symmetry group: A006746, A006747, A006748, A006749, A056877, A056878, A142886, A144553, A144554.
Cf. A001168, A033492, A000104, A054359, A054360, A001419, A000988, A030228 (chiral polyominoes).
See A006765 for another version.
Sequence in context: A148287 A036357 A000104 * A055192 A108555 A032203
Adjacent sequences: A000102 A000103 A000104 * A000106 A000107 A000108
|
|
|
KEYWORD
|
nonn,hard,nice,core
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
Extended to n=28 by Tomas Oliveira e Silva.
Link updated by William Rex Marshall, Dec 16 2009
Edited by Gill Barequet, May 24 2011
|
|
|
STATUS
|
approved
|
| |
|
|
