A000105 -id:A000105 - cp's OEIS frontend

A246521 List of free polyominoes in binary coding, ordered by number of bits, then value of the binary code. Can be read as irregular table with row lengths A000105 (in which case the offset is 0).

0, 1, 3, 7, 11, 15, 23, 27, 30, 75, 31, 47, 62, 79, 91, 94, 143, 181, 182, 188, 406, 1099, 63, 95, 111, 126, 159, 175, 183, 189, 190, 207, 219, 221, 222, 252, 347, 350, 378, 407, 413, 476, 504, 1103, 1115, 1118, 1227, 1244, 2127, 2229, 2230, 2236, 2292, 2451, 2454, 2460, 33867, 127

Offset: 1

M. F. Hasler, Aug 28 2014

nonn

The binary coding (as suggested in a post to the SeqFan list by F. T. Adams-Watters) is obtained by summing the powers of 2 corresponding to the numbers covered by the polyomino, when the points of the quarter-plane are numbered by antidiagonals, and the animal is placed (and flipped/rotated) as to obtain the smallest possible value, which in particular implies pushing it to both borders. See example for further details.
The smallest value for an n-omino is the sum 2^0 + ... + 2^(n-1) = 2^n - 1 = A000225(n), and the largest value, obtained for the straight n-omino, is 2^0 + 2^1 + 2^3 + ... + 2^A000217(n-1) = A181388(n-1).
See A246533 for the variant that lists fixed polyominoes.

			Number the points of the first quadrant as follows:
   ...   ...   ...
    9 13 18 24 31 ...
    5  8 12 17 23 ...
    2  4  7 11 16 ...
    0  1  3  6 10 ...
An animal occupying squares numbered k1, ..., kN will be represented by a term a(n) = 2^k1 + ... + 2^kN, the position and orientation being chosen as to minimize this value:
The "empty" 0-omino is represented by the empty sum equal to 0 = a(1).
The monomino is represented by a square on 0, and the binary code 2^0 = 1 = a(2).
The free domino is rotated to the ".." configuration represented by 2^0 + 2^1 (since this is smaller than the ":" configuration with value 2^0 + 2^2).
The A000105(3) = 2 free triominoes are represented by 2^0 + 2^1 + 2^3 = [...] and 2^0 + 2^1 + 2^2 = [:.]. The latter value is smaller, therefore the L-shaped triomino is listed before the straight one.
From _M. F. Hasler_, Jan 25 2021: (Start)
Writing all N-ominoes on row N, the table begins:
  N | a(m .. m+k), m = 1 + Sum_{j<N} A000105(j), k = A000105(N) - 1
----+--------------------------------------------------------------
  0 | a(1) = 0 = []
  1 | a(2) = 1 = 2^0 = [.]
  2 | a(3) = 3 = 2^0 + 2^1 = [..]
  3 | a(4) = 7 = [:.], a(5) = 11 = [...]
  4 | 15 = [:..], 23 = [::], 27 = [.:.], 30 = [':.], 75 = [....]
... | ...
(End)

John Mason, Table of n, a(n) for n = 1..87147
F. T. Adams-Watters, Re: Sequence proposal by John Mason, SeqFan list, Aug 24 2014

See A246533 and A246559 for lists of fixed and one-sided polyominoes.

Cf. A000105, A000217, A000225, A181388.

More terms from John Mason, Aug 29 2014

A057730 Number of polyominoes (A000105) with perimeter 2n.

Original entry on oeis.org

0, 1, 1, 3, 6, 25, 86, 416, 1988, 10640, 57987, 328956, 1900321, 11204350, 67042778, 406780346

Offset: 1

N. J. A. Sloane, Oct 29 2000

Does this include polyominoes with holes? - Franklin T. Adams-Watters, Sep 12 2006. Answer from R. J. Mathar: Yes! See the illustrations in the links (e.g. perimeter 16, area 7, No 81 or perimeter 16, area 8, No 174).

All lines (sides of cells which are not common to a pair of cells) contribute to the perimeter, including the interior sides of cavities and holes. - R. J. Mathar, Feb 19 2021

Andrew Clarke, Isoperimetrical Polyominoes
Andrew Clarke, Picture from Andrew Clarke's page showing the polyominoes of perimeters 4, 6, 8 and 10.
Gordon Hamilton, Grade 3 area and perimeter activity
R. J. Mathar, perimeter 10
R. J. Mathar, perimeter 12
R. J. Mathar, perimeter 14
R. J. Mathar, Illustrating perimeter 16, area <= 13
R. J. Mathar, Illustrating perimeter 18, area <= 13
R. J. Mathar, Illustrating perimeter 20, area <= 13

Cf. A000105, A002931, A057753, A266549 (same, but holes not allowed), column sums of A342243, A131487 (polyominoes by total number of edges).

Additional comments from Barry Cipra, Jun 08 2004
Link updated by William Rex Marshall, Dec 16 2009
a(9)-a(10) added by Luca Petrone, Jan 08 2016
a(1)-a(9) confirmed by Bert Dobbelaere, Oct 19 2018
a(10)-a(12) corrected and extended by John Mason, Jul 26 2021
a(13)-a(16) added by John Mason, Sep 08 2022

A173271 Partial sums of A000105.

Original entry on oeis.org

1, 2, 3, 5, 10, 22, 57, 165, 534, 1819, 6474, 23547, 87147, 325738, 1227709, 4654285, 17733540, 67841449, 260463501, 1003087733, 3873759683, 14996820361, 58188678049, 226235685777, 881235386180, 3438462430944, 13437551253019

Offset: 0

Jonathan Vos Post, Feb 14 2010

nonn

John Mason, Table of n, a(n) for n = 0..50 (terms 0..48 from Jean-François Alcover).

Cf. A000105, A130866.

Cases[Import["https://oeis.org/A000105/b000105.txt", "Table"], {, }][[All, 2]] // Accumulate (* Jean-François Alcover, Aug 17 2022 *)

a(n) = A130866(n) + 1. - John Mason, Feb 21 2023

A056220 a(n) = 2*n^2 - 1.

Original entry on oeis.org

-1, 1, 7, 17, 31, 49, 71, 97, 127, 161, 199, 241, 287, 337, 391, 449, 511, 577, 647, 721, 799, 881, 967, 1057, 1151, 1249, 1351, 1457, 1567, 1681, 1799, 1921, 2047, 2177, 2311, 2449, 2591, 2737, 2887, 3041, 3199, 3361, 3527, 3697, 3871, 4049, 4231, 4417, 4607, 4801

Offset: 0

N. J. A. Sloane, Aug 06 2000

Image of squares (A000290) under "little Hankel" transform that sends [c_0, c_1, ...] to [d_0, d_1, ...] where d_n = c_n^2 - c_{n+1}*c_{n-1}. - Henry Bottomley, Dec 12 2000
Surround numbers of an n X n square. - Jason Earls, Apr 16 2001
Numbers n such that 2*n + 2 is a perfect square. - Cino Hilliard, Dec 18 2003, Juri-Stepan Gerasimov, Apr 09 2016
The sums of the consecutive integer sequences 2n^2 to 2(n+1)^2-1 are cubes, as 2n^2 + ... + 2(n+1)^2-1 = (1/2)(2(n+1)^2 - 1 - 2n^2 + 1)(2(n+1)^2 - 1 + 2n^2) = (2n+1)^3. E.g., 2+3+4+5+6+7 = 27 = 3^3, then 8+9+10+...+17 = 125 = 5^3. - Andras Erszegi (erszegi.andras(AT)chello.hu), Apr 29 2005
X values (other than 0) of solutions to the equation 2*X^3 + 2*X^2 = Y^2. To find Y values: b(n) = 2n*(2*n^2 - 1). - Mohamed Bouhamida, Nov 06 2007
Average of the squares of two consecutive terms is also a square. In fact: (2*n^2 - 1)^2 + (2*(n+1)^2 - 1)^2 = 2*(2*n^2 + 2*n + 1)^2. - Matias Saucedo (solomatias(AT)yahoo.com.ar), Aug 18 2008
Equals row sums of triangle A143593 and binomial transform of [1, 6, 4, 0, 0, 0, ...] with n > 1. - Gary W. Adamson, Aug 26 2008
Start a spiral of square tiles. Trivially the first tile fits in a 1 X 1 square. 7 tiles fit in a 3 X 3 square, 17 tiles fit in a 5 X 5 square and so on. - Juhani Heino, Dec 13 2009
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-2, A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n >= 1, a(n) = coeff(charpoly(A,x),x^(n-2)). - Milan Janjic, Jan 26 2010
For each n > 0, the recursive series, formula S(b) = 6*S(b-1) - S(b-2) - 2*a(n) with S(0) = 4n^2-4n+1 and S(1) = 2n^2, has the property that every even term is a perfect square and every odd term is twice a perfect square. - Kenneth J Ramsey, Jul 18 2010
Fourth diagonal of A154685 for n > 2. - Vincenzo Librandi, Aug 07 2010
First integer of (2*n)^2 consecutive integers, where the last integer is 3 times the first + 1. As example, n = 2: term = 7; (2*n)^2 = 16; 7, 8, 9, ..., 20, 21, 22: 7*3 + 1 = 22. - Denis Borris, Nov 18 2012
Chebyshev polynomial of the first kind T(2,n). - Vincenzo Librandi, May 30 2014
For n > 0, number of possible positions of a 1 X 2 rectangle in a (n+1) X (n+2) rectangular integer lattice. - Andres Cicuttin, Apr 07 2016
This sequence also represents the best solution for Ripà's n_1 X n_2 X n_3 dots problem, for any 0 < n_1 = n_2 < n_3 = floor((3/2)*(n_1 - 1)) + 1. - Marco Ripà, Jul 23 2018

			a(0) = 0^2-1*1 = -1, a(1) = 1^2 - 4*0 = 1, a(2) = 2^2 - 9*1 = 7, etc.
a(4) = 31 = (1, 3, 3, 1) dot (1, 6, 4, 0) = (1 + 18 + 12 + 0). - _Gary W. Adamson_, Aug 29 2008

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Jeremiah Bartz, Bruce Dearden, and Joel Iiams, Classes of Gap Balancing Numbers, arXiv:1810.07895 [math.NT], 2018.
Milan Janjić, Hessenberg Matrices and Integer Sequences, J. Int. Seq., Vol. 13 (2010), Article # 10.7.8.
Mitch Phillipson, Manda Riehl, and Tristan Williams, Enumeration of Wilf classes in Sn ~ Cr for two patterns of length 3, PU. M. A., Vol. 21, No. 2 (2010), pp. 321-338.
Marco Ripà, The rectangular spiral or the n1 X n2 X ... X nk Points Problem , Notes on Number Theory and Discrete Mathematics, Vol. 20, No. 1 (2014), pp. 59-71.
Leo Tavares, Illustration: Twin Squares
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A000105, A000217, A000290, A000384, A001082, A001653, A001844, A002378, A002593, A003215, A005563, A028347, A036666, A046092, A047875, A062717, A069074, A077585, A087475, A119258, A143593, A154685, A162610, A188653, A225227.
Cf. A066049 (indices of prime terms)
Column 2 of array A188644 (starting at offset 1).

List([0..50], n-> 2*n^2-1); # Muniru A Asiru, Jul 24 2018

[2*n^2-1 : n in [0..50]]; // Vincenzo Librandi, May 30 2014

A056220:=n->2*n^2-1; seq(A056220(n), n=0..50); # Wesley Ivan Hurt, Jun 16 2014

Array[2 #^2 - 1 &, 50, 0] (* Robert G. Wilson v, Jul 23 2018 *)
CoefficientList[Series[(x^2 +4x -1)/(1-x)^3, {x, 0, 50}], x] (* or *)
LinearRecurrence[{3, -3, 1}, {-1, 1, 7}, 51] (* Robert G. Wilson v, Jul 24 2018 *)

PARI
```
a(n)=2*n^2-1;
```

[2*n^2-1 for n in (0..50)] # G. C. Greubel, Jul 07 2019

G.f.: (-1 + 4*x + x^2)/(1-x)^3. - Henry Bottomley, Dec 12 2000
a(n) = A119258(n+1,2) for n > 0. - Reinhard Zumkeller, May 11 2006
From Doug Bell, Mar 08 2009: (Start)
a(0) = -1,
a(n) = sqrt(A001844(n)^2 - A069074(n-1)),
a(n+1) = sqrt(A001844(n)^2 + A069074(n-1)) = sqrt(a(n)^2 + A069074(n-1)*2). (End)
a(n) + a(n+1) + 1 = (2n+1)^2. - Doug Bell, Mar 09 2009
a(n) = a(n-1) + 4*n - 2 (with a(0)=-1). - Vincenzo Librandi, Dec 25 2010
a(n) = A188653(2*n) for n > 0. - Reinhard Zumkeller, Apr 13 2011
a(n) = A162610(2*n-1,n) for n > 0. - Reinhard Zumkeller, Jan 19 2013
a(n) = ( Sum_{k=0..2} (C(n+k,3)-C(n+k-1,3))*(C(n+k,3)+C(n+k+1,3)) ) - (C(n+2,3)-C(n-1,3))*(C(n,3)+C(n+3,3)), for n > 3. - J. M. Bergot, Jun 16 2014
a(n) = j^2 + k^2 - 2 or 2*j*k if n >= 2 and j = n + sqrt(2)/2 and k = n - sqrt(2)/2. - Avi Friedlich, Mar 30 2015
a(n) = A002593(n)/n^2. - Bruce J. Nicholson, Apr 03 2017
a(n) = A000384(n) + n - 1. - Bruce J. Nicholson, Nov 12 2017
a(n)*a(n+k) + 2k^2 = m^2 (a perfect square), m = a(n) + (2n*k), for n>=1. - Ezhilarasu Velayutham, May 13 2019
From Amiram Eldar, Aug 10 2020: (Start)
Sum_{n>=1} 1/a(n) = 1/2 - sqrt(2)*Pi*cot(Pi/sqrt(2))/4.
Sum_{n>=1} (-1)^(n+1)/a(n) = sqrt(2)*Pi*csc(Pi/sqrt(2))/4 - 1/2. (End)
From Amiram Eldar, Feb 04 2021: (Start)
Product_{n>=1} (1 + 1/a(n)) = (Pi/sqrt(2))*csc(Pi/sqrt(2)).
Product_{n>=2} (1 - 1/a(n)) = (Pi/(4*sqrt(2)))*csc(Pi/sqrt(2)). (End)
a(n) = A003215(n) - A000217(n-2)*2. - Leo Tavares, Jun 29 2021
Let T(n) = n*(n+1)/2. Then a(n)^2 = T(2n-2)*T(2n+1) + n^2. - Charlie Marion, Feb 12 2023
E.g.f.: exp(x)*(2*x^2 + 2*x - 1). - Stefano Spezia, Jul 08 2023

A000228 Number of hexagonal polyominoes (or hexagonal polyforms, or planar polyhexes) with n cells.

Original entry on oeis.org

1, 1, 3, 7, 22, 82, 333, 1448, 6572, 30490, 143552, 683101, 3274826, 15796897, 76581875, 372868101, 1822236628, 8934910362, 43939164263, 216651036012, 1070793308942, 5303855973849, 26323064063884, 130878392115834, 651812979669234, 3251215493161062, 16240020734253127, 81227147768301723, 406770970805865187, 2039375198751047333

Offset: 1

N. J. A. Sloane

From Markus Voege, Nov 24 2009: (Start)
On the difference between this sequence and A038147:
The first term that differs is for n=6; for all subsequent terms, the number of polyhexes is larger than the number of planar polyhexes.
If I recall correctly, polyhexes are clusters of regular hexagons that are joined at the edges and are LOCALLY embeddable in the hexagonal lattice.
"Planar polyhexes" are polyhexes that are GLOBALLY embeddable in the honeycomb lattice.
Example: (Planar) polyhex with 6 cells (x) and a hole (O):
.. x x
. x O x
.. x x
Polyhex with 6 cells that is cut open (I):
.. xIx
. x O x
.. x x
This polyhex is not globally embeddable in the honeycomb lattice, since adjacent cells of the lattice must be joined. But it can be embedded locally everywhere. It is a start of a spiral. For n>6 the spiral can be continued so that the cells overlap.
Illegal configuration with cut (I):
.. xIx
. x x x
.. x x
This configuration is NOT a polyhex since the vertex at
.. xIx
... x
is not embeddable in the honeycomb lattice.
One has to keep in mind that these definitions are inspired by chemistry. Hence, potential molecules are often the motivation for these definitions. Think of benzene rings that are fused at a C-C bond.
The (planar) polyhexes are "free" configurations, in contrast to "fixed" configurations as in A001207 = Number of fixed hexagonal polyominoes with n cells.
A000228 (planar polyhexes) and A001207 (fixed hexagonal polyominoes) differ only by the attribute "free" vs. "fixed," that is, whether the different orientations and reflections of an embedding in the lattice are counted.
The configuration
. x x .... x
.. x .... x x
is counted once as free and twice as fixed configurations.
Since most configurations have no symmetry, (A001207 / A000228) -> 12 for n -> infinity. (End)

A. T. Balaban and F. Harary, Chemical graphs V: enumeration and proposed nomenclature of benzenoid cata-condensed polycyclic aromatic hydrocarbons, Tetrahedron 24 (1968), 2505-2516.
A. T. Balaban and Paul von R. Schleyer, "Graph theoretical enumeration of polymantanes", Tetrahedron, (1978), vol. 34, 3599-3609
M. Gardner, Polyhexes and Polyaboloes. Ch. 11 in Mathematical Magic Show. New York: Vintage, pp. 146-159, 1978.
M. Gardner, Tiling with Polyominoes, Polyiamonds and Polyhexes. Chap. 14 in Time Travel and Other Mathematical Bewilderments. New York: W. H. Freeman, pp. 175-187, 1988.
J. V. Knop et al., On the total number of polyhexes, Match, No. 16 (1984), 119-134.
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. 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 and Robert A. Russell, Table of n, a(n) for n = 1..36
Frédéric Chyzak, Ivan Gutman, and Peter Paule, Predicting the number of hexagonal systems with 24 and 25 hexagons, Communications in Mathematical and Computer Chemistry (1999) No. 40, 139-151. See p. 141.
A. Clarke, Polyhexes
F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.
D. Gouyou-Beauchamps and P. Leroux, Enumeration of symmetry classes of convex polyominoes on the honeycomb lattice, arXiv:math/0403168 [math.CO], 2004.
M. Keller, Counting polyforms
D. A. Klarner, Cell growth problems, Canad. J. Math. 19 (1967) 851-863.
J. V. Knop, K. Szymanski, Ž. Jeričević, and N. Trinajstić, On the total number of polyhexes, Match, No. 16 (1984), 119-134.
Greg Malen, Érika Roldán, and Rosemberg Toalá-Enríquez, Extremal {p, q}-Animals, Ann. Comb. (2023), p. 3.
John Mason, Counting polyhexes of size 36, updated Oct 27 2023.
Joseph Myers, Polyomino, polyhex and polyiamond tiling
Ed Pegg, Jr., Illustrations of polyforms
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
N. J. A. Sloane, Illustration of initial terms
N. Trinajstich, Z. Jerievi, J. V. Knop, W. R. Muller and K. Szymanski, Computer Generation of Isomeric Structures, Pure & Appl. Chem., Vol. 55, No. 2, pp. 379-390, 1983.
Eric Weisstein's World of Mathematics, Polyhex.

Equals (A006535 + A030225)/2.
Cf. A036359, A002216, A005963, A000228, A001998, A018190.
Cf. A001207, A057973, A364306.
Cf. also A000105, A000577, A103465, A057779, A258206, A258019.

a(13) from Achim Flammenkamp, Feb 15 1999
a(14) from Brendan Owen, Dec 31 2001
a(15) from Joseph Myers, May 05 2002
a(16)-a(20) from Joseph Myers, Sep 21 2002
a(21) from Herman Jamke (hermanjamke(AT)fastmail.fm), May 05 2007
a(22)-a(30) from John Mason, Jul 18 2023

A000162 Number of 3-dimensional polyominoes (or polycubes) with n cells.

Original entry on oeis.org

1, 1, 2, 8, 29, 166, 1023, 6922, 48311, 346543, 2522522, 18598427, 138462649, 1039496297, 7859514470, 59795121480, 457409613979, 3516009200564, 27144143923583, 210375361379518, 1636229771639924, 12766882202755783

Offset: 1

N. J. A. Sloane and J. H. Conway

Here two polycubes that differ by reflection are considered different. - Joerg Arndt, Apr 26 2023

Number of oriented polyominoes with n cubical cells of the regular tiling with Schläfli symbol {4,3,4}. For oriented polyominoes, chiral pairs are counted as two. - Robert A. Russell, Mar 21 2024

			Table showing total number and numbers with each group order.
-------------------------------------------------------------
The last 7 columns form sequences A066453, A066454, A066273, A066281, A066283, A066287, A066288.
.n ...A000162 ..group:.1.....2...3...4.6.8.24
.1 .........1..........0.....0...0...0.0.0..1
.2 .........1..........0.....0...0...0.0.1..0
.3 .........2..........0.....1...0...0.0.1..0
.4 .........8..........1.....4...1...0.0.2..0
.5 ........29.........17....10...0...0.0.2..0
.6 .......166........127....34...0...3.1.1..0
.7 ......1023........941....71...4...5.0.1..1
.8 ......6922.......6662...246...0..11.0.2..1
.9 .....48311......47771...522...3..11.0.4..0
10 ....346543.....344708..1783..24..24.2.2..0
11 ...2522522....2518713..3765...4..35.0.5..0
12 ..18598427...18585455.12858..18..84.5.7..0
13 .138462649..138434899.27496.151..92.2.8..1
14 1039496297.1039401564.94525..25.174.4.5..0

C. J. Bouwkamp, personal communication.
W. F. Lunnon, Symmetry of cubical and general polyominoes, pp. 101-108 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.
W. F. Lunnon, personal communication.
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).

Nina Bohlmann and Ralf Benölken, Complex Tasks: Potentials and Pitfalls, Mathematics (2020) Vol. 8, No. 10, 1780.
C. J. Bouwkamp, A. J. W. Duijvestijn, & N. J. A. Sloane, Correspondence, 1971.
A. Clarke, Polycubes.
A. Clarke, The 8 tetracubes.
Stanley Dodds, C# program for this sequence.
Kevin L. Gong, Polyominoes Home Page.
M. Keller, Counting polyforms.
David A. Klarner, Some results concerning polyominoes, Fibonacci Quarterly 3 (1965), 9-20.
Jeffrey R. Long and R. H. Holm, Enumeration and structural classification of clusters derived from parent solids ..., J. Amer. Chem. Soc., 116 (1994), 9987-10002.
John Mason, Coordinate sets of examples of polycube symmetry (version 2)
Phillip Thompson, Rust port of Stanley Dodds's algorithm.
Eric Weisstein's World of Mathematics, Polycube.

Cf. A001931, A066453.

Cf. A038119 (unoriented), A371397 (chiral), A007743 (achiral), A001931 (fixed).

a(n) = A066453 + A066454 + A066273 + A066281 + A066283 + A066287 + A066288.
a(n) = 2*A038119 - A007743.
a(n) = A000105 + A006759.
a(n) = A038119(n) + A371397(n) = 2*A371397(n) + A007743(n). - Robert A. Russell, Mar 21 2024

The old value for a(11), 2522572, was corrected by Achim Flammenkamp to 2522522, Feb 15 1999.
a(13)-a(14) from Brendan Owen (brendan_owen(AT)yahoo.com), Dec 27 2001
a(15)-a(16) from Herman Jamke (hermanjamke(AT)fastmail.fm), May 05 2007
a(17)-a(20) from Stanley Dodds, Dec 11 2023
a(21)-a(22) (using Dodds's algorithm) from Phillip Thompson, Feb 07 2024

A000577 Number of triangular polyominoes (or triangular polyforms, or polyiamonds) with n cells (turning over is allowed, holes are allowed, must be connected along edges).

Original entry on oeis.org

1, 1, 1, 3, 4, 12, 24, 66, 160, 448, 1186, 3334, 9235, 26166, 73983, 211297, 604107, 1736328, 5000593, 14448984, 41835738, 121419260, 353045291, 1028452717, 3000800627, 8769216722, 25661961898, 75195166667, 220605519559, 647943626796, 1905104762320, 5607039506627, 16517895669575

Offset: 1

N. J. A. Sloane

If holes are not allowed, we get A070765. - Joseph Myers, Apr 20 2009

It is a consequence of Madras's 1999 pattern theorem that almost all polyiamonds have holes, i.e., lim_{n->oo} A070765(n)/A000577(n) = 0. - Johann Peters, Jan 06 2024

F. Harary, Graphical enumeration problems; in Graph Theory and Theoretical Physics, ed. F. Harary, Academic Press, London, 1967, pp. 1-41.
W. F. Lunnon, Counting hexagonal and triangular polyominoes, pp. 87-100 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.
Ed Pegg, Jr., Polyform puzzles, in Tribute to a Mathemagician, Peters, 2005, pp. 119-125.
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).
P. J. Torbijn, Polyiamonds, J. Rec. Math., 2 (1969), 216-227.

John Mason, Table of n, a(n) for n = 1..52
Ed Pegg, Jr., Illustrations of polyforms
A. Clarke, Polyiamonds
S. T. Coffin, The Puzzling World of Polyhedral Dissections, Chap 2, Table 1.
R. K. Guy, O'Beirne's Hexiamond, in The Mathemagician and the Pied Puzzler - A Collection in Tribute to Martin Gardner, Ed. E. R. Berlekamp and T. Rogers, A. K. Peters, 1999, 85-96 [broken link?]
J. and J. Hindriks, Dutchman Designs: Quilting Patterns [broken link?]
Kadon Enterprises, The 66 polyominoes of order 8 (from a puzzle)
Kadon Enterprises, Home page
M. Keller, Counting polyforms.
N. Madras, A pattern theorem for lattice clusters, arXiv:math/9902161 [math.PR], 1999; Annals of Combinatorics, 3 (1999), 357-384.
Greg Malen, Érika Roldán, and Rosemberg Toalá-Enríquez, Extremal {p, q}-Animals, Ann. Comb. (2023), p. 3.
John Mason, Counting Polyiamonds
R. J. Mathar, Illustrations for up to 9-iamonds
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
Eric Weisstein's World of Mathematics, Polyiamond

Cf. A000207, A006534, A030223, A030224, A001420, A096361, A070765.

Cf. also A000105, A000228, A103465.

More terms from David W. Wilson
a(19) from Achim Flammenkamp, Feb 15 1999
a(20), a(21), a(22), a(23) and a(24) from Brendan Owen (brendan_owen(AT)yahoo.com), Jan 01 2002
a(25) to a(28) from Joseph Myers, Sep 24 2002
Link updated by William Rex Marshall, Dec 16 2009
a(29) and a(30) from Joseph Myers, Nov 21 2010
More terms from John Mason, Oct 28 2023

A001168 Number of fixed polyominoes with n cells.

Original entry on oeis.org

1, 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

Offset: 0

N. J. A. Sloane

Number of rookwise connected patterns of n square cells.

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

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

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 378-382.
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.)
I. Jensen. Counting polyominoes: a parallel implementation for cluster computing. LNCS 2659 (2003) 203-212, ICCS 2003
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. 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).

Gill Barequet and Gil Ben-Shachar, Table of n, a(n) for n = 0..70, a(0)..a(56) from Iwan Jensen.
Michael H. Albert, Christian Bean, Anders Claesson, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, Combinatorial Exploration: An algorithmic framework for enumeration, arXiv:2202.07715 [math.CO], 2022.
G. Barequet and R. Barequet, An Improved Upper Bound on the Growth Constant of Polyominoes, Electronic Notes in Discrete Math., 2015.
Gill Barequet and Gil Ben-Shachar, Counting Polyominoes, Revisited, Proc. Symp. Algor. Eng. Exp. (ALENEX 2024), 133-143.
Gill Barequet, Gil Ben-Shachar, and Martha Carolina Osegueda, Applications of Concatenation Arguments to Polyominoes and Polycubes, EuroCG '20, 36th European Workshop on Computational Geometry, (Würzburg, Germany, 16-18 March 2020).
G. Barequet, M. Moffie, A. Ribo, and G. Rote, Counting polyominoes on twisted cylinders, Integers 6 (2006), A22, 37 pp. (electronic).
Gill Barequet and M. Shalah, Improved Bounds on the Growth Constant of Polyiamonds, 32nd European Workshop on Computational Geometry, 2016.
Gill Barequet, Solomon W. Golomb, and David A. Klarner, Polyominoes. (This is a revision, by G. Barequet, of the chapter of the same title originally written by the late D. A. Klarner for the first edition, and revised by the late S. W. Golomb for the second edition.) Preprint, 2016.
Vuong Bui, An asymptotic lower bound on the number of polyominoes, arXiv:2211.14909 [math.CO], 2022-2023. See footnote 4 for a(69) = 4619282047583828929546825973053580643926 and a(70) = 18500792645885711270652890811942343400814, attributed to Gill Barequet and Gil Ben-Shachar.
Vuong Bui, Bounding Klarner's constant from above using a simple recurrence, arXiv:2412.20143 [math.CO], 2024. See p. 1.
Stirling Chow and Frank Ruskey, Gray codes for column-convex polyominoes and a new class of distributive lattices, Discrete Mathematics, 309 (2009), 5284-5297.
A. R. Conway and A. J. Guttmann, On two-dimensional percolation, J. Phys. A: Math. Gen. 28(1995) 891-904.
Steven R. Finch, Klarner's Lattice Animal Constant [Broken link]
Steven R. Finch, Klarner's Lattice Animal Constant [From the Wayback machine]
J. Fortier, A. Goupil, J. Lortie and J. Tremblay, Exhaustive generation of gominoes, Theoretical Computer Science, 2012. - _N. J. A. Sloane_, Sep 20 2012
I. Jensen, Enumerations of lattice animals and trees, arXiv:cond-mat/0007239.
I. Jensen, Enumerations of lattice animals and trees, J. Stat. Phys. 103 (3-4) (2001) 865-881, Table II.
I. Jensen, Home page
I. Jensen, More terms [Go to series, animals, number of animals]
I. Jensen, More terms [pdf file of lost web link]
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.
D. E. Knuth, Program
D. E. Knuth, First 47 terms
D. E. Knuth, Problems That Philippe Would Have Loved, Paris 2014.
C. Lesieur and L. Vuillon, From Tilings to Fibers - Bio-mathematical Aspects of Fold Plasticity, Chapter 13 (pages 395-422) of "Oligomerization of Chemical and Biological Compounds", book edited by Claire Lesieur, ISBN 978-953-51-1617-2, 2014.
N. Madras, A pattern theorem for lattice clusters, arXiv:math/9902161 [math.PR], 1999; Annals of Combinatorics, 3 (1999), 357-384.
Toufik Mansour and Armend Sh. Shabani, Enumerations on bargraphs, Discrete Math. Lett. (2019) Vol. 2, 65-94.
Tomás Oliveira e Silva, Enumeration of polyominoes
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.
M. F. Sykes and M. Glen, Percolation processes in two dimensions. I. Low-density series expansions, J. Phys. A 9 (1) (1987) 87.
Hugo Tremblay and Julien Vernay, On the generation of discrete figures with connectivity constraints, RAIRO-Theor. Inf. Appl. (2024) Vol. 58, Art. No. 16. See p. 13.
Eric Weisstein's World of Mathematics, Polyomino
Index entries for sequences related to polyominoes

Cf. A000105, A000988, A006746, A056877, A006748, A056878, A006747, A006749, A142886, A144553, row sums of A308359, A210986 (bisection), A210987 (bisection).
A006762 is another version.
Excluding a(0), 8th and 9th row of A366767.

Mathematica
```
See Jaime Rangel-Mondragón's article.
```

For asymptotics, see Knuth (2014).

a(n) = 8*A006749(n) + 4*A006746(n) + 4*A006748(n) + 4*A006747(n) + 2*A056877(n) + 2*A056878(n) + 2*A144553(n) + A142886(n); the number of fixed polyominoes is calculatable according to multiples of the numbers of the various symmetries of the polyomino. - John Mason, Sep 06 2017

Extended to n=28 by Tomás Oliveira e Silva
Extended to n=46 by Iwan Jensen
Verified (and one more term found) by Don Knuth, Jan 09 2001
Richard C. 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
Incorrect Mathematica program removed by Jean-François Alcover, Mar 24 2015
a(0) = 1 added by N. J. A. Sloane, Jun 24 2020

A366766 Array read by antidiagonals, where each row is the counting sequence of a certain type of free polyominoids (see comments).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 3, 2, 1, 0, 1, 0, 1, 7, 5, 0, 1, 0, 1, 0, 1, 20, 16, 0, 1, 1, 0, 1, 0, 1, 60, 55, 0, 2, 1, 1, 0, 1, 0, 1, 204, 222, 0, 5, 2, 2, 1, 0, 1, 0, 1, 702, 950, 0, 12, 5, 5, 0, 1

Offset: 1

Pontus von Brömssen, Oct 22 2023

A (D,d)-polyominoid is a connected set of d-dimensional unit cubes (cells) with integer coordinates in D-dimensional space. For normal polyominoids, two cells are connected if they share a (d-1)-dimensional facet, but here we allow connections where the cells share a lower-dimensional face.
Each row is the counting sequence (by number of cells) of (D,d)-polyominoids with certain restrictions on the allowed connections between cells. Two cells have a connection of type (g,h) if they intersect in a (d-g)-dimensional unit cube and extend in d-h common dimensions. For example, d-dimensional polyominoes use connections of type (1,0), polyplets use connections of types (1,0) (edge connections) and (2,0) (corner connections), normal (3,2)-polyominoids use connections of types (1,0) ("soft" connections) and (1,1) ("hard" connections), hard polyominoids use connections of type (1,1).
Each row corresponds to a triple (D,d,C), where 1 <= d <= D and C is a set of pairs (g,h) with 1 <= g <= d and 0 <= h <= min(g, D-d). The k-th term of that row is the number of free k-celled (D,d)-polyominoids with connections of the types in C. Connections of types not in C are permitted, but the polyominoids must be connected through the specified connections only. For example, polyominoes may have cells that intersect in a point (g = 2) and hard polyominoids can have soft connections (h = 0) that are not needed to keep the polyominoids connected.
The rows are sorted first by D, then by d, and finally by a binary vector indicating which types of connections are allowed, where the connection types (g,h) are sorted lexicographically. (See table in cross-references.)
For each pair (D,d), the first row is 1, 0, 0, ..., corresponding to (D,d,{}) (no connections allowed).
The number of rows corresponding to given values of D and d is 2^((d+1)*(d+2)/2-1) if 2*d <= D and 2^((D-d+1)*(3*d-D+2)/2-1) otherwise.

			Array begins:
  n\k| 1  2  3  4  5   6    7     8      9     10      11       12
  ---+------------------------------------------------------------
   1 | 1  0  0  0  0   0    0     0      0      0       0        0
   2 | 1  1  1  1  1   1    1     1      1      1       1        1
   3 | 1  0  0  0  0   0    0     0      0      0       0        0
   4 | 1  1  1  1  1   1    1     1      1      1       1        1
   5 | 1  1  3  7 20  60  204   702   2526   9180   33989   126713
   6 | 1  2  5 16 55 222  950  4265  19591  91678  434005  2073783
   7 | 1  0  0  0  0   0    0     0      0      0       0        0
   8 | 1  1  2  5 12  35  108   369   1285   4655   17073    63600
   9 | 1  1  2  5 12  35  108   369   1285   4655   17073    63600
  10 | 1  2  5 22 94 524 3031 18770 118133 758381 4915652 32149296
  11 | 1  0  0  0  0   0    0     0      0      0       0        0
  12 | 1  1  1  1  1   1    1     1      1      1       1        1

Pontus von Brömssen, Table of n, a(n) for n = 1..210 (first 20 antidiagonals).
Pontus von Brömssen, Python programs that relate row numbers and parameter sets.
Wikipedia, Polyominoid.
Index entries for sequences related to polyominoes.

Cf. A366767 (fixed), A366768.
The following table lists some sequences that are rows of the array, together with the corresponding values of D, d, and C. Some sequences occur in more than one row. Notation used in the table:
  X: Allowed connection.
  -: Not allowed connection (but may occur "by accident" as long as it is not needed for connectedness).
  .: Not applicable for (D,d) in this row.
  !: d < D and all connections have h = 0, so these polyominoids live in d < D dimensions only.
  *: Whether a connection of type (g,h) is allowed or not is independent of h.
      |   |   | connections  |
      |   |   | g:1122233334 |
    n | D | d | h:0101201230 | sequence
  ----+---+---+--------------+---------
| 1 | 1 | * -......... | A063524
| 1 | 1 | * X......... | A000012
|!2 | 1 | * --........ | A063524
|!2 | 1 |   X-........ | A000012
| 2 | 1 |   -X........ | A361625
| 2 | 1 | * XX........ | A019988
| 2 | 2 | * -.-....... | A063524
| 2 | 2 | * X.-....... | A000105
| 2 | 2 | * -.X....... | A000105
| 2 | 2 | * X.X....... | A030222
|!3 | 1 | * --........ | A063524
|!3 | 1 |   X-........ | A000012
| 3 | 1 |   -X........ | A365654
| 3 | 1 | * XX........ | A365559
|!3 | 2 | * ----...... | A063524
|!3 | 2 |   X---...... | A000105
| 3 | 2 |   -X--...... | A365654
| 3 | 2 | * XX--...... | A075679
|!3 | 2 |   --X-...... | A000105
|!3 | 2 |   X-X-...... | A030222
| 3 | 2 |   -XX-...... | A365995
| 3 | 2 |   XXX-...... | A365997
| 3 | 2 |   ---X...... | A365999
| 3 | 2 |   X--X...... | A366001
| 3 | 2 |   -X-X...... | A366003
| 3 | 2 |   XX-X...... | A366005
| 3 | 2 | * --XX...... | A365652
| 3 | 2 |   X-XX...... | A366007
| 3 | 2 |   -XXX...... | A366009
| 3 | 2 | * XXXX...... | A365650
| 3 | 3 | * -.-..-.... | A063524
| 3 | 3 | * X.-..-.... | A038119
| 3 | 3 | * -.X..-.... | A038173
| 3 | 3 | * X.X..-.... | A268666
| 3 | 3 | * -.-..X.... | A038171
| 3 | 3 | * X.-..X.... | A363205
| 3 | 3 | * -.X..X.... | A363206
| 3 | 3 | * X.X..X.... | A272368
|!4 | 1 | * --........ | A063524
|!4 | 1 |   X-........ | A000012
| 4 | 1 |   -X........ | A366340
| 4 | 1 | * XX........ | A365561
|!4 | 2 | * -----..... | A063524
|!4 | 2 |   X----..... | A000105
| 4 | 2 |   -X---..... | A366338
| 4 | 2 | * XX---..... | A366334
|!4 | 2 |   --X--..... | A000105
|!4 | 2 |   X-X--..... | A030222
  ...
|!4 | 3 | * ----.--... | A063524
|!4 | 3 |   X---.--... | A038119
| 4 | 3 |   -X--.--... | A366340
| 4 | 3 | * XX--.--... | A366336
  ...
| 4 | 4 | * -.-..-...- | A063524
| 4 | 4 | * X.-..-...- | A068870
| 4 | 4 | * -.X..-...- | A365356
| 4 | 4 | * X.X..-...- | A365363
| 4 | 4 | * -.-..X...- | A365354
| 4 | 4 | * X.-..X...- | A365361
| 4 | 4 | * -.X..X...- | A365358
| 4 | 4 | * X.X..X...- | A365365
| 4 | 4 | * -.-..-...X | A365353
| 4 | 4 | * X.-..-...X | A365360
| 4 | 4 | * -.X..-...X | A365357
| 4 | 4 | * X.X..-...X | A365364
| 4 | 4 | * -.-..X...X | A365355
| 4 | 4 | * X.-..X...X | A365362
| 4 | 4 | * -.X..X...X | A365359
| 4 | 4 | * X.X..X...X | A365366
|!5 | 1 | * --........ | A063524
|!5 | 1 |   X-........ | A000012
| 5 | 1 |   -X........ |
| 5 | 1 | * XX........ | A365563

A000104 Number of n-celled free polyominoes without holes.

Original entry on oeis.org

1, 1, 1, 2, 5, 12, 35, 107, 363, 1248, 4460, 16094, 58937, 217117, 805475, 3001127, 11230003, 42161529, 158781106, 599563893, 2269506062, 8609442688, 32725637373, 124621833354, 475368834568, 1816103345752, 6948228104703, 26618671505989, 102102788362303

Offset: 0

N. J. A. Sloane

J. 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 = 0..40
Elena V. Konstantinova and Maxim V. Vidyuk, Discriminating tests of information and topological indices. Animals and trees, J. Chem. Inf. Comput. Sci. 43 (2003), 1860-1871.
John Mason, Description of counting programs
John Mason, Programs for calculation of numbers of unholey polyominoes
Lucia Moura and Ivan Stojmenovic, Backtracking and Isomorph-Free Generation of Polyhexes, Table 2.2 on p. 55 of Handbook of Applied Algorithms (2008).
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
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)
R. C. Read, Contributions to the cell growth problem, Canad. J. Math., 14 (1962), 1-20.

Cf. A000105, row sums of A308300, A006746, A056877, A006748, A056878, A006747, A006749, A054361, A070765 (polyiamonds), A018190 (polyhexes), A266549 (by perimeter).

Cf. A056879, A056880, A056881, A056882, A006724, A357647, A357648.

a(n) = A000105(n) - A001419(n). - John Mason, Sep 06 2022

a(n) = (4*A056879(n) + 4*A056881(n) + 4*A056883(n) + 6*A056880(n) + 6*A056882(n) + 6*A357647(n) + 7*A357648(n) + A006724(n)) / 8. - John Mason, Oct 10 2022

Extended to n=26 by Tomás Oliveira e Silva

a(27)-a(28) from Tomás Oliveira e Silva's page added by Andrey Zabolotskiy, Oct 02 2022

cp's OEIS Frontend

A246521 List of free polyominoes in binary coding, ordered by number of bits, then value of the binary code. Can be read as irregular table with row lengths A000105 (in which case the offset is 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A057730 Number of polyominoes (A000105) with perimeter 2n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A173271 Partial sums of A000105.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A056220 a(n) = 2*n^2 - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A000228 Number of hexagonal polyominoes (or hexagonal polyforms, or planar polyhexes) with n cells.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A000162 Number of 3-dimensional polyominoes (or polycubes) with n cells.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A000577 Number of triangular polyominoes (or triangular polyforms, or polyiamonds) with n cells (turning over is allowed, holes are allowed, must be connected along edges).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A001168 Number of fixed polyominoes with n cells.

Views

Author

Keywords

Comments

Examples

References

Links