# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a000105
Showing 1-1 of 1

%I A000105 M1425 N0561 #245 Mar 21 2024 21:02:09
%S A000105 1,1,1,2,5,12,35,108,369,1285,4655,17073,63600,238591,901971,3426576,
%T A000105 13079255,50107909,192622052,742624232,2870671950,11123060678,
%U A000105 43191857688,168047007728,654999700403,2557227044764,9999088822075,39153010938487,153511100594603
%N A000105 Number of free polyominoes (or square animals) with n cells.
%C A000105 For n>0, 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 A000105 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 A000105 Names for first few polyominoes: monomino, domino, tromino, tetromino, pentomino, hexomino, heptomino, octomino, enneomino, decomino, hendecomino, dodecomino, ...
%C A000105 Limit_{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). The 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 A000105 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 A000105 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.
%C A000105 Conjecture: Almost all polyominoes are holey. In other words, A000104(n)/a(n) tends to 0 for increasing n. - _John Mason_, Dec 11 2021 (This is true, a consequence of Madras's 1999 pattern theorem. - _Johann Peters_, Jan 06 2024)
%D A000105 S. W. Golomb, Polyominoes, Appendix D, p. 152; Princeton Univ. Pr. NJ 1994
%D A000105 J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 229.
%D A000105 D. A. Klarner, The Mathematical Gardner, p. 252 Wadsworth Int. CA 1981
%D A000105 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 A000105 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 A000105 George E. Martin, Polyominoes - A Guide to Puzzles and Problems in Tiling, The Mathematical Association of America, 1996
%D A000105 Ed Pegg, Jr., Polyform puzzles, in Tribute to a Mathemagician, Peters, 2005, pp. 119-125.
%D A000105 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 A000105 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000105 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000105 John Mason, <a href="/A000105/b000105.txt">Table of n, a(n) for n = 0..50</a> (terms 0..45,47 from Toshihiro Shirakawa)
%H A000105 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 A000105 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 A000105 K. S. Brown, <a href="http://www.mathpages.com/home/kmath039.htm">Polyomino Enumerations</a>
%H A000105 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 A000105 Juris Čerņenoks and 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 A000105 A. Clarke, <a href="http://www.recmath.com/PolyPages/PolyPages/Polyominoes.html">Polyominoes</a>
%H A000105 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 A000105 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 A000105 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 A000105 M. Keller, <a href="http://www.solitairelaboratory.com/polyenum.html">Counting polyforms</a>.
%H A000105 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 A000105 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 A000105 John Mason, <a href="/A000105/a000105_1.pdf">Counting size 50 polyominoes</a>
%H A000105 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 A000105 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 A000105 W. R. Muller, K. Szymanski, J. V. Knop, and N. Trinajstic, <a href="https://doi.org/10.1007/BF01130823">On the number of square-cell configurations</a>, Theor. Chim. Acta 86 (1993) 269-278
%H A000105 Joseph Myers, <a href="http://www.polyomino.org.uk/mathematics/polyform-tiling/">Polyomino tiling</a>
%H A000105 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 A000105 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 A000105 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 A000105 Anuj Pathania, <a href="https://doi.org/10.5445/IR/1000082991">Scalable Task Schedulers for Many-Core Architectures</a>, Ph.D. Thesis, Karlsruher Instituts für Technologie (Germany, 2018).
%H A000105 Ed Pegg, Jr., <a href="http://demonstrations.wolfram.com/PolyformExplorer/">Illustrations of polyforms</a>
%H A000105 Henri Picciotto, <a href="http://www.mathedpage.org/puzzles/polyo/index.html"> Polyomino Lessons</a>
%H A000105 Jaime Rangel-Mondragón, <a href="https://web.archive.org/web/20190411024906/http://www.mathematica-journal.com/issue/v9i3/polyominoes.html">Polyominoes and Related Families</a>, The Mathematica Journal, Volume 9, Issue 3.
%H A000105 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 A000105 D. H. Redelmeier, <a href="/A056877/a056877.png">Table 3</a> of Counting polyominoes...
%H A000105 Toshihiro Shirakawa, <a href="https://www.gathering4gardner.org/g4g10gift/math/Shirakawa_Toshihiro-Harmonic_Magic_Square.pdf">Harmonic Magic Square, pp 3-4: Enumeration of Polyominoes considering the symmetry</a>, April 2012.
%H A000105 Herman Tulleken, <a href="https://www.researchgate.net/publication/333296614_Polyominoes">Polyominoes 2.2: How they fit together</a>, (2019).
%H A000105 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Polyomino.html">Polyomino</a>
%H A000105 Wikipedia, <a href="https://commons.wikimedia.org/wiki/File:All_35_free_hexominoes.svg">The 35 hexominoes</a>
%H A000105 Wikipedia, <a href="https://commons.wikimedia.org/wiki/File:Heptominoes.svg">The 108 heptominoes</a>
%H A000105 Wikipedia, <a href="https://commons.wikimedia.org/wiki/File:All_369_free_octominoes.svg">The 369 octominoes</a>
%H A000105 Wikipedia, <a href="https://en.wikipedia.org/wiki/Polyomino">Polyomino</a>
%H A000105 D. Xu, T. Horiyama, T. Shirakawa and R. Uehara, <a href="https://doi.org/10.1007/978-3-319-17142-5_21">Common Developments of Three Incongruent Boxes of Area 30</a>, in Proc. 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, LNCS Vol. 9076, pp. 236-247.
%H A000105 L. Zucca, <a href="http://www.iread.it/lz/pag1_eng.html">Pentominoes</a>
%H A000105 L. Zucca, <a href="/A000105/a000105.gif">The 12 pentominoes</a>
%H A000105 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A000105 a(n) = A000104(n) + A001419(n). - _R. J. Mathar_, Jun 15 2014
%F A000105 a(n) = A006749(n) + A006746(n) + A006748(n) + A006747(n) + A056877(n) + A056878(n) + A144553(n) + A142886(n). - _Andrew Howroyd_, Dec 04 2018
%F A000105 a(n) = A259087(n) + A259088(n). - _R. J. Mathar_, May 22 2019
%F A000105 a(n) = (4*A006746(n) + 4*A006748(n) + 4*A006747(n) + 6*A056877(n) + 6*A056878(n) + 6*A144553(n) + 7*A142886(n) + A001168(n))/8. - _John Mason_, Nov 14 2021
%e A000105 a(0) = 1 as there is 1 empty polyomino with #cells = 0. - _Fred Lunnon_, Jun 24 2020
%t A000105 (* In this program by Jaime Rangel-Mondragón, polyominoes are represented as a list of Gaussian integers. *)
%t A000105 polyominoQ[p_List] := And @@ ((IntegerQ[Re[#]] && IntegerQ[Im[#]])& /@ p);
%t A000105 rot[p_?polyominoQ] := I*p;
%t A000105 ref[p_?polyominoQ] := (# - 2 Re[#])& /@ p;
%t A000105 cyclic[p_] := Module[{i = p, ans = {p}}, While[(i = rot[i]) != p, AppendTo[ans, i]]; ans];
%t A000105 dihedral[p_?polyominoQ] := Flatten[{#, ref[#]}& /@ cyclic[p], 1];
%t A000105 canonical[p_?polyominoQ] := Union[(# - (Min[Re[p]] + Min[Im[p]]*I))& /@ p];
%t A000105 allPieces[p_] := Union[canonical /@ dihedral[p]];
%t A000105 polyominoes[1] = {{0}};
%t A000105 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]];
%t A000105 a[n_] := a[n] = Length[ polyominoes[n]];
%t A000105 Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 12}] (* _Jean-François Alcover_, Mar 24 2015, after Jaime Rangel-Mondragón *)
%Y A000105 Sequences classifying polyominoes by symmetry group: A006746, A006747, A006748, A006749, A056877, A056878, A142886, A144553, A144554.
%Y A000105 Cf. A001168 (not reduced by D_8 symmetry), A000104 (no holes), A054359, A054360, A001419, A000988, A030228 (chiral polyominoes).
%Y A000105 See A006765 for another version.
%Y A000105 Cf. also A000577, A000228, A103465, A210996 (bisection).
%Y A000105 Excluding a(0), 8th and 9th row of A366766.
%K A000105 nonn,hard,nice,core
%O A000105 0,4
%A A000105 _N. J. A. Sloane_
%E A000105 Extended to n=28 by Tomás Oliveira e Silva
%E A000105 Link updated by _William Rex Marshall_, Dec 16 2009
%E A000105 Edited by _Gill Barequet_, May 24 2011
%E A000105 Misspelling "polyominos" corrected by _Don Knuth_, May 03 2016
%E A000105 a(29)-a(45), a(47) from Toshihiro Shirakawa
%E A000105 a(46) calculated using values from A001168 (I. Jensen), A006748/A056877/A056878/A144553/A142886 (_Robert A. Russell_) and A006746/A006747 (_John Mason_), Nov 14 2021

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE