A001168 -id:A001168 - cp's OEIS frontend

A187276 Number of d+/d- diagonally convex polyominoes with n cells.

1, 2, 6, 19, 61, 196, 630, 2024, 6499, 20860, 66941, 214797, 689201, 2211347, 7095226, 22765414, 73044113, 234366327, 751978494, 2412768983, 7741517800, 24839137696, 79697907919, 255715662623

Offset: 1

David Bevan, Mar 07 2011

nonn

A polyomino is d+ [d-] convex if the intersection of its interior with any line of slope 1 [-1] through the centers of the cells is connected.

			A(5) = 61 = A001168(5) - 2, omitting two of the orientations of the V pentomino.

M. Bousquet-Mélou and R. Brak, "Exactly Solved Models", in A. J. Guttmann, ed., Polygons, Polyominoes and Polycubes, Springer, 2009, pp. 46 & 76.

Cf. A001168 (fixed polyominoes), A001169 (row-convex polyominoes).

ab[n_,m_,q_]:=Sum[q[n-m-r,k],{r,1,m},{k,m+1-r,n-m-r}]
bb[n_,m_,q_]:=Sum[q[n-m-r,m-r],{r,1,m-1}]+Sum[q[n-m-r,k],{r,1,m-1},{k,m-r,n-m-r}]
cb[n_,m_,q_]:=Sum[q[n-m-r,m-1-r],{r,1,m-2}]
a[n_,m_]:=0/;n<=1||m<=0
a[n_,m_]:=a[n,m]=Sum[(k-m)p[n-m,k],{k,m+1,n-m}]+ab[n,m,b]+2ab[n,m,c]+Sum[(r-1)c[n-m-r,m+1-r],{r,2,m}]
b[1,1]=1;
b[n_,m_]:=0/;n<=1||m<=0
b[n_,m_]:=b[n,m]=2Sum[p[n-m,k],{k,m,n-m}]+bb[n,m,b]+2bb[n,m,c]+2Sum[(r-1)c[n-m-r,m-r],{r,2,m-1}]
c[n_,m_]:=0/;n<=1||m<=0
c[n_,m_]:=c[n,m]=p[n-m,m-1]+cb[n,m,b]+2cb[n,m,c]+Sum[(r-1)c[n-m-r,m-1-r],{r,2,m-2}]
p[n_,m_]:=a[n,m]+b[n,m]+c[n,m]
Table[Sum[p[n,m],{m,(n+1)/2}],{n,20}]

Typo in example corrected by David Bevan, Mar 23 2013

A210987 Number of fixed polyominoes with 2n-1 cells.

Original entry on oeis.org

1, 6, 63, 760, 9910, 135268, 1903890, 27394666, 400795844, 5940738676, 88983512783, 1344372335524, 20457802016011, 313224032098244, 4820975409710116, 74541651404935148, 1157186142148293638, 18027932215016128134

Offset: 1

Omar E. Pol, Sep 16 2012

nonn

Eric Weisstein's World of Mathematics, Polyomino
Wikipedia, Polyomino

Bisection of A001168.

Cf. A210986, A210989, A210997.

a(n) = A001168(2*n-1).

A216820 Number of polyominoes of site-perimeter n with 8-holes allowed.

Original entry on oeis.org

1, 0, 2, 4, 12, 32, 110, 340, 1209, 4272, 16166, 61848, 246660, 1004883, 4209124, 18020832, 78898047, 352437205, 1605225878, 7445515638, 35142033027, 168644213617, 822311934788, 4071431204506, 20457850555113

Offset: 4

N. J. A. Sloane, Sep 20 2012

This sequence counts fixed connected (via common edges) polyominoes with given site-perimeter. The site-perimeter of a polyomino is the number of cells that are adjacent to it (via common edges). This sequence allows holes of any kind; A216819 allows holes but requires them to be connected to each other and to the exterior area via common corners; A216818 doesn't allow holes. - Andrey Zabolotskiy, Feb 02 2022

			The only polyomino with site-perimeter 4 is a single cell.
No polyominoes have site-perimeter 5.
a(6) = 2: the domino, rotated (or reflected) in 2 possible ways.
a(7) = 4: the L-tromino, rotated in 4 ways.
a(8) = 12: the X-pentomino; the square tetromino; the straight tromino, rotated in 2 ways; the T-tetromino, rotated in 4 ways; the skew tetromino, rotated and reflected in 4 ways.

A. R. Conway and A. J. Guttmann, On two-dimensional percolation, J. Phys. A: Math. Gen., 28 (1995), 891-904. See Table 2.
J. Fortier, A. Goupil, J. Lortie and J. Tremblay, Exhaustive generation of gominoes, Theoretical Computer Science, 502 (2013), 76-87. See Table 1, beware of the typo in a(15).

Cf. A216818 (no holes), A216819 (holes connected by corners); A001168 (by area), A057730 (by perimeter); A366443 (free).

a(15) corrected, a(16)-a(28) from Conway & Guttmann added by Andrey Zabolotskiy, Feb 02 2022

A385715 Square array read by descending antidiagonals: A(n,k) is the number of fixed n-dimensional (n,2)-polyominoids, n >= 2, of size k >= 1.

Original entry on oeis.org

1, 2, 3, 6, 18, 6, 19, 158, 60, 10, 63, 1611, 916, 140, 15, 216, 17811, 16698, 3060, 270, 21, 760, 207395, 336210, 81090, 7690, 462, 28, 2725, 2505858, 7218768, 2396434, 268005, 16226, 728, 36, 9910, 31125711, 162185112, 76020890, 10477161, 701589, 30408, 1080, 45

Offset: 2

John Mason, Jul 07 2025

			The top corner of the array (size on horizontal axis, dimensions on vertical):
              1    2     3       4         5          6           7           8         9         10
(A001168) 2:  1    2     6      19        63        216         760        2725      9910      36446
(A075678) 3:  3   18   158    1611     17811     207395     2505858    31125711 394982973 5098498323
(A366335) 4:  6   60   916   16698    336210    7218768   162185112  3769221330
          5: 10  140  3060   81090   2396434   76020890  2535403620 87781527395
          6: 15  270  7690  268005  10477161  441378400 19603138320
          7: 21  462 16226  701589  34160301 1796996509
          8: 28  728 30408 1570436  91583156
          9: 36 1080 52296 3141108 213477012

Wikipedia, Polyominoid.
Index entries for sequences related to polyominoes.

Rows: A001168 (n=2), A075678 (n=3), A366335 (n=4).
Columns: A000217 (k=1), A213820 (k=2).
Cf. A385291 (polyominoes), A385581 (polysticks).

A387002 Triangle read by rows: T(n,d) is the number of fixed, properly d-dimensional (d,2)-polyominoids of size n, 2 <= d <= n+1.

Original entry on oeis.org

1, 2, 12, 6, 140, 320, 19, 1554, 10368, 13520, 63, 17622, 265344, 892864, 786432, 216, 206747, 6390484, 41998840, 89389920, 58383808, 760, 2503578, 152166240, 1749529040, 6773387520

Offset: 1

Pontus von Brömssen, Aug 14 2025

A (d,2)-polyominoid consists of unit square cells with integer coordinates in the d-dimensional grid, where two cells are connected if they share an edge. The polyominoid is properly d-dimensional if it is not contained in a (d-1)-dimensional affine subspace.

			Triangle begins:
  n\d |     2          3           4           5          6        7  8  9 10 11
  ----+-------------------------------------------------------------------------
   1  |     1
   2  |     2         12
   3  |     6        140         320
   4  |    19       1554       10368       13520
   5  |    63      17622      265344      892864     786432
   6  |   216     206747     6390484    41998840   89389920 58383808
   7  |   760    2503578   152166240  1749529040 6773387520        ?  ?
   8  |  2725   31117536  3644734836 69246650605          ?        ?  ?  ?
   9  |  9910  394953243 88344741448           ?          ?        ?  ?  ?  ?
  10  | 36446 5098388985           ?           ?          ?        ?  ?  ?  ?  ?

Wikipedia, Polyominoid.
Index entries for sequences related to polyominoes.

Cf. A001168 (column d=2), A195739 (polyominoes), A385582 (polysticks), A385715, A387004 (free).

T(n,d) = Sum_{k=2..d} (-1)^(d-k)*binomial(d,k)*A385715(k,n), i.e., the n-th row is the inverse binomial transform of the n-th column of A385715 (with the convention that T(n,d) = A385715(d,n) = 0 when d <= 1).

A057409 Number of self-avoiding polygons of area n with any number of (self-avoiding polygon) holes on square lattice (not allowing rotations).

Original entry on oeis.org

1, 2, 6, 19, 63, 216, 756, 2685, 9650, 35018, 128084, 471623, 1746492, 6499356, 24290272, 91123171, 342984175, 1294829776, 4901319978, 18597856445, 70723784744, 269486503694, 1028736811230, 3933715966653

Offset: 1

N. J. A. Sloane, Aug 30 2000

nonn

I. Jensen, Table of n, a(n) for n = 1..40 (from link below)
Anthony J. Guttmann, Iwan Jensen and Aleksander L. Owczarek, Polygonal polyominoes on the square lattice, J. Phys. A: Math. Gen., 34 (2001), 3721-3733.
I. Jensen, More terms

Cf. A006724 (no holes, first differs at n=8), A057406, A057407, A057408 (resp. 1, 2, 3 holes); A001168 (any holes, first differs at n=7); A088702 (by perimeter); A000104 (no holes, rotations and reflections allowed).

A196593 Number of fixed tree-like convex polyominoes.

Original entry on oeis.org

1, 2, 6, 18, 51, 134, 328, 758, 1677, 3594, 7530, 15530, 31687, 64190, 129420, 260142, 521889, 1045730, 2093806, 4190402, 8384091, 16772022, 33548496, 67102118, 134210101, 268426874, 536861298, 1073731098, 2147471727, 4294954094, 8589920020, 17179853150

Offset: 1

Gill Barequet, Oct 04 2011

In a 1-1 mapping with permutations that avoid the patterns (1423, 4213, 2314, 2431, 2413, <3142,{2},{2}>) (the fourth pattern is bivincular).

Harvey P. Dale, Table of n, a(n) for n = 1..1000
Gadi Aleksandrowicz, Andrei Asinowski and Gill Barequet, A polyominoes-permutations injection and tree-like convex polyominoes, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, Pages 503-520
A. Goupil, H. Cloutier, and F. Nouboud, Enumeration of inscribed polyominos, FPSCA 2010 (San Francisco) DMTS proc. AN 2010, 737-748, eq. (10)
Index entries for linear recurrences with constant coefficients, signature (6,-14,16,-9,2).

Cf. A001168 (fixed polyominoes), A066158 (fixed tree polyominoes), A067675 (fixed convex polyominoes).

LinearRecurrence[{6,-14,16,-9,2},{1,2,6,18,51},50] (* Harvey P. Dale, Oct 16 2011 *)

G.f.: (x*(1-4*x+8*x^2-6*x^3+4*x^4))/((1-x)^4*(1-2*x)).
a(n) = 6*a(n-1) - 14*a(n-2) + 16*a(n-3) - 9*a(n-4) + 2*a(n-5).
a(n) = 2^(n+2) - (n^3-n^2+10*n+4)/2.

A272435 Number of n-ominoes in n X n grid (i.e., rookwise connected sets of n cells in a square array with n rows and n columns).

Original entry on oeis.org

1, 4, 22, 113, 571, 2816, 13616, 64678, 302574, 1397318, 6382660, 28882214, 129640058, 577812724, 2559491834, 11276000877, 49437494408, 215815377168

Offset: 1

Don Knuth, Apr 29 2016

Higher corrected values are supported by exhibiting a(n) distinct n-ominoes in the n-square for n=10 and n=11 (see LINKS below). - James Stein, Dec 11 2017

a(n) is the number of connected induced subgraphs with n vertices in the n X n grid graph. - Andrew Howroyd, Apr 27 2020

			The 22 arrangements for n=3 include three horizontal rows, three vertical rows, and four ways to place each rotation of the L-tromino.

This sequence will some day be mentioned in an exercise in section 7.2.2 of The Art of Computer Programming.

James Stein, 1397318 gzipped 10-ominoes
James Stein, 6382660 gzipped 11-ominoes
Eric Weisstein's World of Mathematics, Grid Graph

Cf. A001168, A059525, A162676.

a(10)-a(12) corrected, and a(13)-a(14) added by James Stein, Dec 11 2017
a(15)-a(16) from Andrew Howroyd, Apr 27 2020
a(17)-a(18) from Giovanni Resta, May 01 2020

A283108 Number of fixed polyominoes minus number of free polyominoes for order n.

Original entry on oeis.org

0, 0, 1, 4, 14, 51, 181, 652, 2356, 8625, 31791, 118195, 442261, 1665299, 6302903, 23968090, 91513682, 350687935, 1348198490, 5198114444, 20094107710, 77860452105, 302340714990, 1176325327796, 4584989069865, 17900574971247, 69993587545033, 274071021159757, 1074577571232370

Offset: 0

Francois Alcover, Feb 28 2017

nonn

a(n) is the number of fixed polyominoes that are a transform -- except through identity -- of a canonical polyomino.
E.g., n=3:
       A001168
  ______|_________
 |                  |
  A000105 | A283108
  canon   | transform
          |
  *       |
  *       |
  *       |  * * *
          |
  *       |    *   * *   * *
  * *     |  * *     *   *

John Mason, Table of n, a(n) for n = 0..50

Cf. A000105, A001168.

a(n) = A001168(n) - A000105(n).

A283110 Increase in the number of fixed polyominoes from order n to order n+1.

Original entry on oeis.org

0, 1, 4, 13, 44, 153, 544, 1965, 7185, 26536, 98822, 370593, 1398029, 5300984, 20189792, 77198271, 296202907, 1140024698, 4399918134, 17024040984, 66018733123, 256549059895, 998839762846, 3895616434744, 15217813245743, 59534874351097, 233231355731136, 914864639728729

Offset: 0

Francois Alcover, Feb 28 2017

nonn

John Mason, Table of n, a(n) for n = 0..55

Cf. A001168.

a(n) = A001168(n+1) - A001168(n); this holds for n=0 if A001168(0) is set conventionally to 1, like it is done for free polyominoes in A000105. We say there are exactly 1 fixed polyominoes of order 0.

cp's OEIS Frontend

A187276 Number of d+/d- diagonally convex polyominoes with n cells.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

Extensions

A210987 Number of fixed polyominoes with 2n-1 cells.

Views

Author

Keywords

Links

Crossrefs

Formula

A216820 Number of polyominoes of site-perimeter n with 8-holes allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A385715 Square array read by descending antidiagonals: A(n,k) is the number of fixed n-dimensional (n,2)-polyominoids, n >= 2, of size k >= 1.

Views

Author

Keywords

Examples

Links

Crossrefs

A387002 Triangle read by rows: T(n,d) is the number of fixed, properly d-dimensional (d,2)-polyominoids of size n, 2 <= d <= n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A057409 Number of self-avoiding polygons of area n with any number of (self-avoiding polygon) holes on square lattice (not allowing rotations).

Views

Author

Keywords

Links

Crossrefs

A196593 Number of fixed tree-like convex polyominoes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A272435 Number of n-ominoes in n X n grid (i.e., rookwise connected sets of n cells in a square array with n rows and n columns).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A283108 Number of fixed polyominoes minus number of free polyominoes for order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A283110 Increase in the number of fixed polyominoes from order n to order n+1.

Views