A268371 -id:A268371 - cp's OEIS frontend

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

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

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

A268416 Number of aligned free polyominoes that will fit in a square of size n X n.

Original entry on oeis.org

1, 4, 35, 1280, 262292, 205515653, 592830103236

Offset: 1

John Mason, Feb 04 2016

a(n) is the number of free polyominoes that have both width and height <= n. Compare this to Craig Knecht's A268311 which has both height and width = n. The word "aligned" in the title refers to the restriction that the polyominoes have edges parallel to the sides of the square, in contrast with A268427.

Cf. A268311, A268371, A268427.

a(n) = Sum_{i=1..n*(n+1)/2} A268371(i). - John Mason, Sep 11 2024

a(6) from Talmon Silver, Jul 29 2020

a(7) from John Mason, Sep 11 2024

A268404 Number of fixed polyominoes that have a width and height of n.

Original entry on oeis.org

1, 5, 111, 7943, 1890403, 1562052227, 4617328590967, 49605487608825311, 1951842619769780119767, 282220061839181920696642671, 150134849621798165832163223922131, 293909551918134914019004192289440616787, 2116817972794640259940977362779552773322908743

Offset: 1

Craig Knecht, Feb 03 2016

nonn

Iwan Jensen originally provided this sequence.
The sequence also describes the water patterns of lakes in the water retention model.
A lake is defined as a body of water with dimensions of n X n when the size of the square is (n+2) X (n+2). All other bodies of water are ponds.
The 3 X 3 square serves as a tutorial for the following three nomenclatures: (1) The total number of distinct water patterns is 102 and includes lakes and ponds. (2) The number of free lake-type polyominoes is 24. (3) The number of fixed lake-type polyominoes is 111. See the explanatory graphics in the link section.
John Mason has looked at free polyominoes in rectangles; see A268371.
Anna Skelt initiated the discussion on the definition of a lake.

			There are many interesting ways to connect all boundaries of the square with the smallest number of edge-joined cells.
  0 0 0 0 1 0
  0 0 0 0 1 1
  0 0 1 1 1 0
  0 0 1 0 0 0
  1 1 1 0 0 0
  0 1 0 0 0 0

Andrew Howroyd, Table of n, a(n) for n = 1..15
Craig Knecht, 4x4 minimal lake area patterns
Craig Knecht, 5x5 minimal lake area patterns
Craig Knecht, 6x6 minimal lake area patterns
Craig Knecht, 7x7 minimal lake area patterns
Craig Knecht, 24 free lake-type polyominoes 3x3
Craig Knecht, Polyominoe enumeration
Craig Knecht, Walter Trump's 111 fixed lake-type polyominoes 3x3
Wikipedia, Water Retention on Mathematical Surfaces

Main diagonal of A292357.

Cf. A054247 (all unique water retention patterns for an n X n square), A268311 (free polyominoes that connect all boundaries on a square), A268339 (lake patterns that are invariant to all transformations).

A292357 = Cases[Import["https://oeis.org/A292357/b292357.txt", "Table"], {, }][[All, 2]];
a[n_] := A292357[[2n^2 - 2n + 1]];
Array[a, 15] (* Jean-François Alcover, Sep 10 2019 *)

a(12)-a(13) from Andrew Howroyd, Oct 02 2017

A335711 The number of free polyominoes of width 2 and height n.

Original entry on oeis.org

2, 6, 12, 30, 65, 158, 362, 875, 2064, 4984, 11914, 28764, 69155, 166956, 402372, 971413, 2343518, 5657754, 13654968, 32966010, 79577189, 192116330, 463786190, 1119678911, 2703086892, 6525829036, 15754607062, 38034986040, 91824246215, 221683340568, 535190123592

Offset: 2

R. J. Mathar, Jun 18 2020

nonn

The second column of A268371.

			a(2)=2, bounding box 2 X 2, counts the L-shaped 3-omino and the full block 4-omino.
a(3)=6, bounding box 2 X 3, counts three 4-ominoes, two 5-omioes, and the full 2 X 3 block 6-omino.
a(4)=12, bounding box 2 X 4, counts three 5-ominoes, six 6-ominoes, two 7-ominoes, and the full 2 X 4 block 8-omino.

Cf. A268371, A107769 (asymmetric), A005409 (C_2 symmetry and higher), A352720 (width 2 and size n).

Conjecture: a(n) = A107769(n-1) + A005409(floor((n+3)/2)).
Conjectures from Colin Barker, Jun 24 2020: (Start)
G.f.: x^2*(2 - 8*x^2 + 2*x^3 - x^4 + x^5 + x^6) / ((1 - x)*(1 - 2*x - x^2)*(1 - 2*x^2 - x^4)).
a(n) = 3*a(n-1) + a(n-2) - 7*a(n-3) + 3*a(n-4) - a(n-5) + a(n-6) + a(n-7) for n>8.
(End)
a(n) = (2*r(n) + 2*m(n) + A078057(n) + 1) / 4, where r(n) = A078057(floor((n-1)/2) - 1)/2, and m(n) = A078057(floor((n+1)/2) - 3)/2. - John Mason, Feb 28 2022

a(12)-a(20) from Jean-Luc Manguin, Jun 23 2020
a(21)-a(28) from John Mason, Feb 27 2022
a(29)-a(32) from John Mason, Feb 28 2022

A336267 Number of free polyominoes of width 3 and height n.

Original entry on oeis.org

1, 6, 24, 181, 941, 4662, 23691, 119271, 603760, 3050402, 15428576, 78004550, 394462578, 1994595585, 10086050889, 51001111356, 257894037378, 1304071170194, 6594196094078, 33344335235915, 168609627579175, 852594638783225, 4311246376730011

Offset: 1

Jean-Luc Manguin, Jul 15 2020

nonn

The sequence can be generated using a series of recursive formulas in a fashion similar to A353067. - John Mason, Nov 04 2022

			a(2)=6, bounding box 2 X 3 as in A335711.

John Mason, Table of n, a(n) for n = 1..400

Cf. A268371, A335711, A353067.

More terms from John Mason, Nov 04 2022

cp's OEIS Frontend

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

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

A268416 Number of aligned free polyominoes that will fit in a square of size n X n.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A268404 Number of fixed polyominoes that have a width and height of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A335711 The number of free polyominoes of width 2 and height n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A336267 Number of free polyominoes of width 3 and height n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions