A308359 -id:A308359 - cp's OEIS frontend

A001168 Number of fixed polyominoes with n cells.

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

A292357 Array read by antidiagonals: T(m,n) is the number of fixed polyominoes that have a width of m and height of n.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 15, 15, 1, 1, 39, 111, 39, 1, 1, 97, 649, 649, 97, 1, 1, 237, 3495, 7943, 3495, 237, 1, 1, 575, 18189, 86995, 86995, 18189, 575, 1, 1, 1391, 93231, 910667, 1890403, 910667, 93231, 1391, 1

Offset: 1

Andrew Howroyd, Oct 02 2017

Equivalently, the number of m X n binary arrays with all 1's connected and at least one 1 on each edge.

			Array begins:
===============================================================
m\n| 1   2     3       4         5           6             7
---|-----------------------------------------------------------
1  | 1   1     1       1         1           1             1...
2  | 1   5    15      39        97         237           575...
3  | 1  15   111     649      3495       18189         93231...
4  | 1  39   649    7943     86995      910667       9339937...
5  | 1  97  3495   86995   1890403    38916067     782256643...
6  | 1 237 18189  910667  38916067  1562052227   61025668579...
7  | 1 575 93231 9339937 782256643 61025668579 4617328590967...
...
T(2,2) = 5 counts 4 3-ominoes of shape 2x2 and 1 4-omino of shape 2x2.
T(3,2) = 15 counts 8 4-ominoes of shape 3x2, 6 5-ominoes of shape 3x2, and 1 6-omino of shape 3x2.
T(4,2) = 39 counts 12 5-ominoes of shape 4x2, 18 6-ominoes of shape 4x2, 8 7-ominoes of shape 4x2, and 1 8-omino of shape 4x2.

Andrew Howroyd, Table of n, a(n) for n = 1..435
Andrew Howroyd, Fixed polyominoes by width, height and number of cells
Louis Marin, Counting Polyominoes in a Rectangle b X h, arXiv:2406.16413 [cs.DM], 2024. See p. 145.
Index entries for sequences related to polyominoes

Rows 2..4 are A034182, A034184, A034187.
Main diagonal is A268404.
Cf. A268371 (nonequivalent), A287151, A308359.

A287151 = Import["https://oeis.org/A287151/b287151.txt", "Table"][[All, 2]];
imax = Length[A287151];
mmax = Sqrt[2 imax] // Ceiling;
Clear[V]; VV = Table[V[m-n+1, n], {m, 1, mmax}, {n, 1, m}] // Flatten;
Do[Evaluate[VV[[i]]] = A287151[[i]], {i, 1, imax}];
V[0, ] = V[, 0] = 0;
T[m_, n_] := If[m == 1 || n == 1, 1, U[m, n] - 2 U[m, n-1] + U[m, n-2]];
U[m_, n_] := V[m, n] - 2 V[m-1, n] + V[m-2, n];
Table[T[m-n+1, n], {m, 1, mmax}, {n, 1, m}] // Flatten // Take[#, imax]& (* Jean-François Alcover, Sep 22 2019 *)

T(m, n) = U(m, n) - 2*U(m, n-1) + U(m, n-2) where U(m, n) = V(m, n) - 2*V(m-1, n) + V(m-2, n) and V(m, n) = A287151(m, n).

A027053 a(n) = T(n,n+2), T given by A027052.

Original entry on oeis.org

1, 4, 9, 18, 35, 66, 123, 228, 421, 776, 1429, 2630, 4839, 8902, 16375, 30120, 55401, 101900, 187425, 344730, 634059, 1166218, 2145011, 3945292, 7256525, 13346832, 24548653, 45152014, 83047503, 152748174, 280947695, 516743376

Offset: 2

Clark Kimberling

Second differences of (A027026(n)-1)/2.
Pairwise sums of A089068.
a(n) is also the number of fixed polyominoes with n cells of height (or width) 2. - David Bevan, Sep 09 2009

G. C. Greubel, Table of n, a(n) for n = 2..1001
Doron Zeilberger, The generating functions and series expansions for 2D lattice-animals of globally bounded width. [Local copies of generating functions and series expansions].
Index entries for sequences related to polyominoes
Index entries for linear recurrences with constant coefficients, signature (2,0,0,-1).

2nd column of A308359.

a:=[1,4,9,18];; for n in [5..30] do a[n]:=2*a[n-1]-a[n-4]; od; a; # G. C. Greubel, Nov 05 2019

R:=PowerSeriesRing(Integers(), 32); Coefficients(R!( x^2*(1+x)^2/((1-x)*(1-x-x^2-x^3)) )); // G. C. Greubel, Nov 05 2019

seq(coeff(series(x^2*(1+x)^2/((1-x)*(1-x-x^2-x^3)), x, n+1), x, n), n = 2 ..30); # G. C. Greubel, Nov 05 2019

LinearRecurrence[{2,0,0,-1}, {1,4,9,18}, 30] (* G. C. Greubel, Nov 05 2019 *)

my(x='x+O('x^32)); Vec(x^2*(1+x)^2/((1-x)*(1-x-x^2-x^3))) \\ G. C. Greubel, Nov 05 2019

def A027053_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P(x^2*(1+x)^2/((1-x)*(1-x-x^2-x^3))).list()
a=A027053_list(32); a[2:] # G. C. Greubel, Nov 05 2019

G.f.: x^2*(1+x)^2/((1-x)*(1-x-x^2-x^3)).
a(n) = A089068(n-1) + A089068(n).
a(n) = a(n-1) + a(n-2) + a(n-3) + 4. - David Bevan, Sep 09 2009
a(n) = A001590(n+3) - 2. - David Bevan, Sep 09 2009
a(n+1) - a(n) = A000213(n+1). - R. J. Mathar, Aug 04 2013

A157608 Array read by antidiagonals, giving number of fixed hexagonal polyominoes of height up to n/2 and with hexagonal cell count k.

Original entry on oeis.org

0, 1, 0, 1, 0, 0, 1, 2, 0, 0, 1, 3, 2, 0, 0, 1, 3, 6, 2, 0, 0, 1, 3, 10, 11, 2, 0, 0, 1, 3, 11, 25, 19, 2, 0, 0, 1, 3, 11, 37, 61, 32, 2, 0, 0, 1, 3, 11, 43, 111, 142, 53, 2, 0, 0, 1, 3, 11, 44, 153, 320, 323, 87, 2, 0, 0, 1, 3, 11, 44, 177, 514, 896, 723, 142, 2, 0, 0

Offset: 1

Jonathan Vos Post, Mar 02 2009

			The array begins:
================================================
n=1 | 0 | 0 |  0 |  0 |   0 |   0 |   0 |    0 |
n=2 | 1 | 0 |  0 |  0 |   0 |   0 |   0 |    0 |
n=3 | 1 | 2 |  2 |  2 |   2 |   2 |   2 |    2 |
n=4 | 1 | 3 |  6 | 11 |  19 |  32 |  53 |   87 |
n=5 | 1 | 3 | 10 | 25 |  61 | 142 | 323 |  723 |
n=6 | 1 | 3 | 11 | 37 | 111 | 320 | 896 | 2461 |
================================================

Moa Apagodu (formerly Mohamud Mohammed) and Stirling Chow, Counting hexagonal lattice animals confined to a strip, arXiv:math/0202295v5 [math.CO], 2009. See Table 1.
Moa Apagodu, Maple programs.

Cf. A001170, A001207, A059716, A068091, A308359.

T(4, 4) = 11:
                                               
   / \/ \ / \/ \  / \         / \   / \   / \
  / \/ \/ \/ \/ \ \/ \/ \ / \/ \/ / \/ \ / \/ \
  \/ \/     \/ \/   \/ \/ \/ \/  / \/ \/ \/ \/ \
                          \/     \/    \/             \/
                              _
   / \  / \/ \  / \/ \   / \  / \
  / \/ \ \/ \/  \/ \/ / \/  \/ \_
  \/ \/   \/ \  / \/  / \/ \  / \/ \
    \/       \/  \/    \/ \/  \/ \_/

T(n, k) = A001207(k) for n >= 2*k. - Andrey Zabolotskiy, Aug 31 2024

Definition not clear to me! "Height" refers to the lattice or to the polyominoes? - N. J. A. Sloane, Mar 14 2009

Name clarified and more terms added by Andrey Zabolotskiy, Aug 24 2024

A335606 The number of fixed n-ominoes with a convex hull of width 3.

Original entry on oeis.org

1, 8, 31, 95, 269, 721, 1866, 4728, 11804, 29162, 71502, 174342, 423341, 1024786, 2474934, 5966625, 14365256, 34550674, 83035396, 199440433, 478814076, 1149133511, 2757142136, 6613933242, 15863281135, 38042981575, 91225540813, 218739876078, 524464594304, 1257437814143, 3014693395137

Offset: 3

R. J. Mathar, Jun 15 2020

Obtained from Zeilberger's tables by subtracting the numbers of width <= 3 and of width <= 2.

			a(3)=1 counts 1 3-omino of shape 1x3.
a(4)=8 counts 8 4-ominoes of shape 2x3.
a(5)=31 counts 6 5-ominoes of shape 2x3 and 25 5-ominoes of shape 3x3.
a(6)=95 counts 1 6-omino of shape 2x3, 44 6-ominoes of shape 3x3 and 50 6-ominoes of shape 4x3.

D. Zeilberger, Series expansion for 2D lattice-animals of globally bounded width
Index entries for sequences related to polyominoes
Index entries for linear recurrences with constant coefficients, signature (5,-6,-4,8,1,2,-8,0,-1,9,-2,-1,-3,1).

Cf. A308359, A027053 (width 2).

LinearRecurrence[{5, -6, -4, 8, 1, 2, -8, 0, -1, 9, -2, -1, -3, 1}, {1, 8, 31, 95, 269, 721, 1866, 4728, 11804, 29162, 71502, 174342, 423341, 1024786, 2474934}, 31] (* Georg Fischer, Jan 16 2021 *)

a(n) = A308359(n,3).
G.f.: -x^3*(1+x) *(x^10 -x^9 -3*x^8 +2*x^7 -x^6 -2*x^5 +7*x^4 -3*x^3 -5*x^2 +2*x +1) / ( (x-1) *(x^3 +x^2 +x -1) *(x^10 -3*x^9 -x^8 +2*x^6 +x^4 -4*x^3 +3*x -1) ).
a(n)= 5*a(n-1) -6*a(n-2) -4*a(n-3) +8*a(n-4) +a(n-5) +2*a(n-6) -8*a(n-7) -a(n-9) +9*a(n-10) -2*a(n-11) -a(n-12) -3*a(n-13) +a(n-14).

cp's OEIS Frontend

A001168 Number of fixed polyominoes with n cells.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A292357 Array read by antidiagonals: T(m,n) is the number of fixed polyominoes that have a width of m and height of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A027053 a(n) = T(n,n+2), T given by A027052.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A157608 Array read by antidiagonals, giving number of fixed hexagonal polyominoes of height up to n/2 and with hexagonal cell count k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A335606 The number of fixed n-ominoes with a convex hull of width 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula