A000104 -id:A000104 - cp's OEIS frontend

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

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

Offset: 0

N. J. A. Sloane

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
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, ...
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).
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.
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.
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)

			a(0) = 1 as there is 1 empty polyomino with #cells = 0. - _Fred Lunnon_, Jun 24 2020

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.
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.
George E. Martin, Polyominoes - A Guide to Puzzles and Problems in Tiling, The Mathematical Association of America, 1996
Ed Pegg, Jr., Polyform puzzles, in Tribute to a Mathemagician, Peters, 2005, pp. 119-125.
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.
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).

John Mason, Table of n, a(n) for n = 0..50 (terms 0..45,47 from Toshihiro Shirakawa)
Z. Abel, E. Demaine, M. Demaine, H. Matsui and G. Rote, Common Developments of Several Different Orthogonal Boxes.
G. Barequet, M. Moffie, A. Ribo and G. Rote, Counting polyominoes on twisted cylinders, Integers 6 (2006), A22, 37 pp. (electronic).
K. S. Brown, Polyomino Enumerations
G. Castiglione, A. Frosini, E. Munarini, A. Restivo and S. Rinaldi, Combinatorial aspects of L-convex polyominoes, European J. Combin. 28 (2007), no. 6, 1724-1741.
Juris Čerņenoks and Andrejs Cibulis, Tetrads and their Counting, Baltic J. Modern Computing, Vol. 6 (2018), No. 2, 96-106.
A. Clarke, Polyominoes
A. R. Conway and A. J. Guttmann, On two-dimensional percolation, J. Phys. A: Math. Gen. 28(1995) 891-904.
I. Jensen, Enumerations of lattice animals and trees, arXiv:cond-mat/0007239 [cond-mat.stat-mech], 2000.
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.
M. Keller, Counting polyforms.
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.
N. Madras, A pattern theorem for lattice clusters, arXiv:math/9902161 [math.PR], 1999; Annals of Combinatorics, 3 (1999), 357-384.
John Mason, Counting size 50 polyominoes -V2
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.
Stephan Mertens and Markus E. Lautenbacher, Counting lattice animals: A parallel attack J. Stat. Phys., vol. 66, no. 1/2, pp. 669-678, 1992.
W. R. Muller, K. Szymanski, J. V. Knop, and N. Trinajstic, On the number of square-cell configurations, Theor. Chim. Acta 86 (1993) 269-278
Joseph Myers, Polyomino tiling
Tomás Oliveira e Silva, Animal enumerations on regular tilings in Spherical, Euclidean and Hyperbolic 2-dimensional spaces
Tomás Oliveira e Silva, Animal enumerations on the {4,4} Euclidean tiling [The enumeration to order 28]
T. R. Parkin, L. J. Lander, and D. R. Parkin, Polyomino Enumeration Results, presented at SIAM Fall Meeting, 1967, and accompanying letter from T. J. Lander (annotated scanned copy)
Anuj Pathania, Scalable Task Schedulers for Many-Core Architectures, Ph.D. Thesis, Karlsruher Instituts für Technologie (Germany, 2018).
Ed Pegg, Jr., Illustrations of polyforms
Henri Picciotto, Polyomino Lessons
Jaime Rangel-Mondragón, Polyominoes and Related Families, The Mathematica Journal, Volume 9, Issue 3.
D. H. Redelmeier, Counting polyominoes: yet another attack, Discrete Math., 36 (1981), 191-203.
D. H. Redelmeier, Table 3 of Counting polyominoes...
Toshihiro Shirakawa, Harmonic Magic Square, pp 3-4: Enumeration of Polyominoes considering the symmetry, April 2012.
Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).
Eric Weisstein's World of Mathematics, Polyomino
Wikipedia, The 35 hexominoes
Wikipedia, The 108 heptominoes
Wikipedia, The 369 octominoes
Wikipedia, Polyomino
D. Xu, T. Horiyama, T. Shirakawa and 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.
L. Zucca, Pentominoes
L. Zucca, The 12 pentominoes
Index entries for "core" sequences

Sequences classifying polyominoes by symmetry group: A006746, A006747, A006748, A006749, A056877, A056878, A142886, A144553, A144554.
Cf. A001168 (not reduced by D_8 symmetry), A000104 (no holes), A054359, A054360, A001419, A000988, A030228 (chiral polyominoes).
See A006765 for another version.
Cf. also A000577, A000228, A103465, A210996 (bisection).
Excluding a(0), 8th and 9th row of A366766.

(* 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 *)

a(n) = A000104(n) + A001419(n). - R. J. Mathar, Jun 15 2014
a(n) = A006749(n) + A006746(n) + A006748(n) + A006747(n) + A056877(n) + A056878(n) + A144553(n) + A142886(n). - Andrew Howroyd, Dec 04 2018
a(n) = A259087(n) + A259088(n). - R. J. Mathar, May 22 2019
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

Extended to n=28 by Tomás Oliveira e Silva
Link updated by William Rex Marshall, Dec 16 2009
Edited by Gill Barequet, May 24 2011
Misspelling "polyominos" corrected by Don Knuth, May 03 2016
a(29)-a(45), a(47) from Toshihiro Shirakawa
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

A006749 Number of asymmetric polyominoes with n cells.

Original entry on oeis.org

0, 0, 0, 1, 5, 20, 84, 316, 1196, 4461, 16750, 62878, 237394, 899265, 3422111, 13069026, 50091095, 192583152, 742560511, 2870523142, 11122817672, 43191285751, 168046076423, 654997492842, 2557223459805, 9999080270766, 39152997087077, 153511067364760

Offset: 1

N. J. A. Sloane

This sequence counts polyominoes whose symmetry group has order 1.

A. R. Conway and A. J. Guttmann, On two-dimensional percolation, J. Phys. A: Math. Gen. 28(1995) 891-904.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

John Mason, Table of n, a(n) for n = 1..50 (This version corrects erroneous values from a(44) onwards in previous version.)
Tomás Oliveira e Silva, Enumeration of polyominoes
T. R. Parkin, L. J. Lander, and D. R. Parkin, Polyomino Enumeration Results, presented at SIAM Fall Meeting, 1967, and accompanying letter from T. J. Lander (annotated scanned copy). See page 21.
D. H. Redelmeier, Counting polyominoes: yet another attack, Discrete Math., 36 (1981), 191-203.
D. H. Redelmeier, Table 3 of Counting polyominoes...

Cf. A000105, A001168, A006746, A056877, A006748, A056878, A006747, A006749.

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

a(n) + A259090(n) = A000105(n). - R. J. Mathar, Sep 29 2021

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

A001419 Number of n-celled polyominoes with holes.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 6, 37, 195, 979, 4663, 21474, 96496, 425449, 1849252, 7946380, 33840946, 143060339, 601165888, 2513617990, 10466220315, 43425174374, 179630865835, 741123699012, 3050860717372, 12534339432498, 51408312232300, 210526591157926, 860989703302456

Offset: 1

N. J. A. Sloane

From John Mason, Sep 06 2022: (Start)
Conjecture: Almost all polyominoes are holey. In other words, a(n)/A000105(n) tends to 1 for increasing n.
The number of holes in a polyomino is given by the formula (based on a generalization of Pick's Theorem): H = n + 1 - i - s / 2, where:
n is the size (area) of the polyomino;
i is the number of completely internal vertices; i.e., the number of vertices that are surrounded by 4 squares;
s is the number of vertices on a single border; i.e., vertices that are the corners of 1, 2 or 3 squares, but excluding those that touch only 2 squares that are diagonally adjacent. (End)

S. W. Golomb, Polyominoes. Scribner's, NY, 1965; second edition ( Polyominoes: Puzzles, Packings, Problems and Patterns) Princeton Univ. Press, 1994.
Joseph S. Madachy, "Pentominoes - Some Solved and Unsolved Problems", J. Rec. Math., 2 (1969), 181-188.
George E. Martin, Polyominoes - A Guide to Puzzles and Problems in Tiling, The Mathematical Association of America, 1996
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).

John Mason, Table of n, a(n) for n = 1..40
W. R. Muller, K. Szymanski, J. V. Knop, and N. Trinajstic, On the number of square-cell configurations, Theor. Chim. Acta 86 (1993) 269-278.
Joseph Myers, Polyomino tiling
T. R. Parkin, L. J. Lander, and D. R. Parkin, Polyomino Enumeration Results, presented at SIAM Fall Meeting, 1967, and accompanying letter from T. J. Lander (annotated scanned copy).
R. C. Read, Contributions to the cell growth problem, Canad. J. Math., 14 (1962), 1-20.
Eric Weisstein's World of Mathematics, Polyomino.
Wikipedia, The 6 Octominoes with holes
Wikipedia, The 37 Nonominoes with holes

Cf. A000104, A000105.

A[s_] := With[{s6 = StringPadLeft[ToString[s], 6, "0"]}, Cases[ Import[ "https://oeis.org/A" <> s6 <> "/b" <> s6 <> ".txt", "Table"], {, }][[All, 2]]];
A000104 = A@104;
A000105 = A@105;
a[n_] := A000105[[n + 1]] - A000104[[n + 1]];
a /@ Range[40] (* Jean-François Alcover, Jan 04 2020, updated Apr 21 2024 after John Mason's b-file *)

a(n) >= A057418(n). - R. J. Mathar, Jun 15 2014

a(n) = A000105(n) - A000104(n). - Jean-François Alcover, Jan 04 2020, after R. J. Mathar in A000105.

More terms from Joseph Myers, May 05 2002
More terms from Joseph Myers, Nov 04 2003
a(24)-a(26) from Joseph Myers, Nov 17 2010
More terms from John Mason, Oct 10 2022

A103473 Number of polyominoes consisting of 7 regular unit n-gons.

Original entry on oeis.org

24, 108, 551, 333, 558, 1605, 4418, 8350, 17507, 13512, 17775, 30467, 55264, 83252, 134422, 112514, 135175, 195122, 294091, 397852, 566007, 495773, 568602, 751172, 1031920, 1307384, 1729686, 1557663, 1737915, 2169846, 2808616, 3413064

Offset: 3

Sascha Kurz, Feb 07 2005

nonn

			a(3)=24 because there are 24 polyiamonds consisting of 7 triangles and a(4)=108 because there are 108 polyominoes consisting of 7 squares.

Matthias Koch and Sascha Kurz, Enumeration of generalized polyominoes, arXiv:math.CO/0605144
S. Kurz, k-polyominoes.

Cf. A103469, A103470, A103471, A103472.

Cf. A000577, A000104, A000228, A103465, A103466, A103467, A103468, A103469, A103470, A103471, A103472, A115071, A120102, A120103, A120104.

More terms from Sascha Kurz, Jun 09 2006

A268311 Number of free polyominoes that form a continuous path of edge joined cells spanning an n X n square in both dimensions.

Original entry on oeis.org

1, 2, 24, 1051, 238048, 195284973, 577169894573, 6200686124225191

Offset: 1

Craig Knecht, Jan 31 2016

This idea originated from the water retention model for mathematical surfaces and is identical to the concept of a "lake". A lake is body of water that has dimensions of (n-2) X (n-2) when the square size is n X n. All other bodies of water are "ponds".

Iwan Jensen with his transfer matrix algorithm provided the number of symmetrically redundant solutions. Walter Trump enumerated the symmetrically unique solutions.

			The cells with value 1 show the smallest possible lake in this 4 X 4 square:
1 1 1 1
0 0 0 1
0 0 0 1
0 0 0 1
a(3)=24 = 6+7+7+3+1: There fit 6 5-ominoes in a 3x3 square, 7 6-ominoes in a 3x3 square, 7 7-ominoes in a 3x3 square, 3 8-ominoes in a 3x3 square, a 1 9-omino in a 3x3 square. - _R. J. Mathar_, Jun 07 2020

Craig Knecht, Polyominoes enumeration
Craig Knecht, Connective polyominoes 3x3
R. J. Mathar, Corrigendum to "Polyomino Enumeration Results (Parkin et al, SIAM Fall Meeting 1967)" viXra:1905.0474 (2019)
R. Parkin, L. J. Lander, and D. R. Parkin, Polyomino Enumeration Results, presented at SIAM Fall Meeting, 1967, and accompanying letter from T. J. Lander (annotated scanned copy) page 9 (incorrect at n=15).
Wikipedia, Connective Polyominoes 4x4
Wikipedia, Connective Polyominoes 5x5
Wikipedia, Connective polyominoes with 4 sym-axis
Wikipedia, Pond larger than a lake
Wikipedia, Water Retention on Mathematical Surfaces
Index entries for sequences related to polyominoes

Cf. A054247 (all unique water retention patterns). Diagonal of A268371.

Cf. A259088.

a(6) corrected. Craig Knecht, May 25 2020

cp's OEIS Frontend

A036357 Erroneous version of A000104.

Views

Author

Keywords

Links

A214610 Erroneous version of A000104.

Views

Author

Keywords

Links

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A006749 Number of asymmetric polyominoes with n cells.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A001419 Number of n-celled polyominoes with holes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A103473 Number of polyominoes consisting of 7 regular unit n-gons.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A268311 Number of free polyominoes that form a continuous path of edge joined cells spanning an n X n square in both dimensions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A120102 Number of polyominoes consisting of 8 regular unit n-gons.

Views

Author

Keywords

Examples

Links

Crossrefs

A120104 Number of polyominoes consisting of 10 regular unit n-gons.

Views

Author

Keywords

Examples

Links

Crossrefs

A070765 Number of polyiamonds with n cells, without holes.

Views

Author