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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000105 Number of free polyominoes (or square animals) with n cells.
(Formerly M1425 N0561)
98

%I M1425 N0561

%S 1,1,1,2,5,12,35,108,369,1285,4655,17073,63600,238591,901971,3426576,

%T 13079255,50107909,192622052,742624232,2870671950,11123060678,

%U 43191857688,168047007728,654999700403,2557227044764,9999088822075,39153010938487,153511100594603

%N Number of free polyominoes (or square animals) with n cells.

%C 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

%C 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

%C Names for first few polyominoes: monomino, domino, tromino, tetromino, pentomino, hexomino, heptomino, octomino, enneomino, decomino, hendecomino, dodecomino, ...

%C 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).

%C Polyominoes are worth exploring in the elementary school classroom. Students in grade 2 can reproduce the first 6 terms. Grade 3 students can explore area and perimeter. Grade 4 students can talk about polyomino symmetries.

%C The pentominoes should be singled out for special attention: 1) they offer a nice, manageable set that a teacher can commercially acquire without too much expense. 2) There are also deeply strategic games and perplexing puzzles that are great for all students. 3) A fraction of students will become engaged because of the beautiful solutions.

%D S. W. Golomb, Polyominoes, Appendix D, p. 152; Princeton Univ. Pr. NJ 1994

%D J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 229.

%D D. A. Klarner, The Mathematical Gardner, p. 252 Wadsworth Int. CA 1981

%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 George E. Martin, Polyominoes - A Guide to Puzzles and Problems in Tiling, The Mathematical Association of America, 1996

%D Ed Pegg, Jr., Polyform puzzles, in Tribute to a Mathemagician, Peters, 2005, pp. 119-125.

%D 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 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).

%D D. Xu, T. Horiyama, T. Shirakawa, R. Uehara, Common Developments of Three Incongruent Boxes of Area 30, in Proc. 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, LNCS Vol. 9076, pp. 236-247.

%H Toshihiro Shirakawa, <a href="/A000105/b000105.txt">Table of n, a(n) for n=0 ..45</a>

%H Z. Abel, E. Demaine, M. Demaine, H. Matsui and G. Rote, <a href="http://2011.cccg.ca/PDFschedule/papers/paper49.pdf">Common Developments of Several Different Orthogonal Boxes</a>.

%H Barequet, Gill; Moffie, Micha; Ribo, Ares; and Rote, Guenter, <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 K. S. Brown, <a href="http://www.mathpages.com/home/kmath039.htm">Polyomino Enumerations</a>

%H G. Castiglione, A. Frosini, E. Munarini, A. Restivo and S. Rinaldi, <a href="http://dx.doi.org/10.1016/j.ejc.2006.06.020">Combinatorial aspects of L-convex polyominoes</a>, European J. Combin. 28 (2007), no. 6, 1724-1741.

%H Juris Čerņenoks, Andrejs Cibulis, <a href="https://doi.org/10.22364/bjmc.2018.6.2.01">Tetrads and their Counting</a>, Baltic J. Modern Computing, Vol. 6 (2018), No. 2, 96-106.

%H A. Clarke, <a href="http://www.recmath.com/PolyPages/PolyPages/Polyominoes.html">Polyominoes</a>

%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 I. Jensen, <a href="http://arxiv.org/abs/cond-mat/0007239">Enumerations of lattice animals and trees</a>, arXiv:cond-mat/0007239 [cond-mat.stat-mech], 2000.

%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>, Journal of Physics A: Mathematical and General, vol. 33, pp. L257-L263, 2000.

%H M. Keller, <a href="http://www.solitairelaboratory.com/polyenum.html">Counting polyforms</a>.

%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 N. Madras, <a href="http://arxiv.org/abs/math/9902161">A pattern theorem for lattice clusters</a>, Annals of Combinatorics, 3 (1999), 357-384.

%H S. Mertens, <a href="http://dx.doi.org/10.1007/BF01026565">Lattice animals: a fast enumeration algorithm and new perimeter polynomials</a>, J. Statistical Physics, vol. 58, no. 5/6, pp. 1095-1108, Mar. 1990.

%H Stephan Mertens and Markus E. Lautenbacher. <a href="http://dx.doi.org/10.1007/BF01060088">Counting lattice animals: A parallel attack</a> J. Stat. Phys., vol. 66, no. 1/2, pp. 669-678, 1992.

%H Joseph Myers, <a href="http://www.polyomino.org.uk/mathematics/polyform-tiling/">Polyomino tiling</a>

%H Tomás Oliveira e Silva, <a href="http://sweet.ua.pt/tos/animals.html">Animal enumerations on regular tilings in Spherical, Euclidean and Hyperbolic 2-dimensional spaces</a>

%H Tomás Oliveira e Silva, <a href="http://sweet.ua.pt/tos/animals/a44.html">Animal enumerations on the {4,4} Euclidean tiling</a> [The enumeration to order 28]

%H T. R. Parkin, L. J. Lander, and D. R. Parkin, <a href="/A000104/a000104.pdf">Polyomino Enumeration Results</a>, presented at SIAM Fall Meeting, 1967) and accompanying letter from T. J. Lander (annotated scanned copy)

%H Ed Pegg, Jr., <a href="http://demonstrations.wolfram.com/PolyformExplorer/">Illustrations of polyforms</a>

%H Henri Picciotto, <a href="http://www.mathedpage.org/puzzles/polyo/index.html"> Polyomino Lessons</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/">Counting polyominoes: yet another attack</a>, Discrete Math., 36 (1981), 191-203.

%H D. H. Redelmeier, <a href="/A056877/a056877.png">Table 3</a> of Counting polyominoes...

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Polyomino.html">Polyomino</a>

%H Wikipedia, <a href="http://upload.wikimedia.org/wikipedia/commons/a/ac/All_369_free_octominoes.svg">The 369 octominoes</a>

%H L. Zucca, <a href="http://www.iread.it/lz/pag1_eng.html">Pentominoes</a>

%H L. Zucca, <a href="/A000105/a000105.gif">The 12 pentominoes</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F a(n) = A000104(n) + A001419(n). - _R. J. Mathar_, Jun 15 2014

%t (* In this program by Jaime Rangel-Mondragón, polyominoes are represented as a list of Gaussian integers. *) polyominoQ[p_List] := And @@ ((IntegerQ[Re[#]] && IntegerQ[Im[#]]) & /@ p); rot[p_?polyominoQ] := I*p; ref[p_?polyominoQ] := (# - 2 Re[#]) & /@ p; cyclic[p_] := Module[{i = p, ans = {p}}, While[(i = rot[i]) != p, AppendTo[ans, i]]; ans]; dihedral[p_?polyominoQ] := Flatten[{#, ref[#]} & /@ cyclic[p], 1]; canonical[p_?polyominoQ] := Union[(# - (Min[Re[p]] + Min[Im[p]]*I)) & /@ 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["a(", n, ") = ", a[n]]; a[n], {n, 1, 12}] (* _Jean-François Alcover_, Mar 24 2015, after Jaime Rangel-Mondragón *)

%Y Sequences classifying polyominoes by symmetry group: A006746, A006747, A006748, A006749, A056877, A056878, A142886, A144553, A144554.

%Y Cf. A001168 (not reduced by D_8 symmetry), A033492, A000104, A054359, A054360, A001419, A000988, A030228 (chiral polyominoes).

%Y See A006765 for another version.

%Y Cf. also A000577, A000228, A103465.

%K nonn,hard,nice,core,changed

%O 0,4

%A _N. J. A. Sloane_

%E Extended to n=28 by Tomás Oliveira e Silva

%E Link updated by _William Rex Marshall_, Dec 16 2009

%E Edited by _Gill Barequet_, May 24 2011

%E Misspelling "polyominos" corrected by _Don Knuth_, May 03 2016

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 23:02 EDT 2018. Contains 316431 sequences. (Running on oeis4.)