A292357 -id:A292357 - cp's OEIS frontend

A034182 Number of not-necessarily-symmetric n X 2 crossword puzzle grids.

1, 5, 15, 39, 97, 237, 575, 1391, 3361, 8117, 19599, 47319, 114241, 275805, 665855, 1607519, 3880897, 9369317, 22619535, 54608391, 131836321, 318281037, 768398399, 1855077839, 4478554081, 10812186005, 26102926095, 63018038199, 152139002497, 367296043197

Offset: 1

Erich Friedman

n X 2 binary arrays with a path of adjacent 1's and no path of adjacent 0's from top row to bottom row. - R. H. Hardin, Mar 21 2002

Define a triangle with T(n,1) = T(n,n) = n*(n-1) + 1, n>=1, and its interior terms via T(r,c) = T(r-1,c) + T(r-1,c-1)+ T(r-2,c-1), 2<=cJ. M. Bergot, Mar 16 2013

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Louis Marin, Counting Polyominoes in a Rectangle b X h, arXiv:2406.16413 [cs.DM], 2024. See p. 145.
Index entries for linear recurrences with constant coefficients, signature (3,-1,-1)

Row 2 of A292357.
Column sums of A059678.
Cf. A001333, A034184, A034187, A052542 (first differences).

a034182 n = a034182_list !! (n-1)
a034182_list = 1 : 5 : (map (+ 4) $
   zipWith (+) a034182_list (map (* 2) $ tail a034182_list))
-- Reinhard Zumkeller, May 23 2013

{1}~Join~NestList[{#2, 2 #2 + #1 + 4} & @@ # &, {1, 5}, 28][[All, -1]] (* Michael De Vlieger, Oct 02 2017 *)

a(n) = 2a(n-1) + a(n-2) + 4.
(1 + 5x + 15x^2 + ...) = (1 + 2x + 2x^2 + ...) * (1 + 3x + 7x^2 + ...), convolution of A040000 and left-shifted A001333.
a(n) = (-4 + (1-sqrt(2))^(1+n) + (1+sqrt(2))^(1+n))/2. G.f.: x*(1+x)^2/((1-x)*(1 - 2*x - x^2)). - Colin Barker, May 22 2012
a(n) = A001333(n+1)-2. - R. J. Mathar, Mar 28 2013
a(n) = A048739(n-3) +2*A048739(n-2) +A048739(n-1). - R. J. Mathar, Jun 15 2020

A287151 Array read by antidiagonals: T(m,n) = number of nonzero m X n binary arrays with all 1's connected.

Original entry on oeis.org

1, 3, 3, 6, 13, 6, 10, 40, 40, 10, 15, 108, 218, 108, 15, 21, 275, 1126, 1126, 275, 21, 28, 681, 5726, 11506, 5726, 681, 28, 36, 1664, 28992, 116166, 116166, 28992, 1664, 36, 45, 4040, 146642, 1168586, 2301877, 1168586, 146642, 4040, 45, 55, 9779, 741556, 11749134, 45280509, 45280509, 11749134, 741556, 9779, 55

Offset: 1

Andrew Howroyd, May 20 2017

Also the number of connected induced (non-null) subgraphs of the grid graph P_m X P_n.

All rows (or columns) are linear recurrences with constant coefficients and the order of the recurrence of row m is at most 1 + A378941(m+1). At least for columns up to 7, this bound gives the actual order of the recurrence. The second differences of any column give those arrays that touch the top and bottom boundaries and have a recurrence order of 2 less since a finite state machine to enumerate these does not require states for empty rows. The number of states required is also considered in A140662 but does not take symmetry into account. - Andrew Howroyd, Dec 18 2024

			Table starts:
====================================================================
m\n|  1    2      3        4         5           6             7
---|----------------------------------------------------------------
1  |  1    3      6       10        15          21            28 ...
2  |  3   13     40      108       275         681          1664 ...
3  |  6   40    218     1126      5726       28992        146642 ...
4  | 10  108   1126    11506    116166     1168586      11749134 ...
5  | 15  275   5726   116166   2301877    45280509     889477656 ...
6  | 21  681  28992  1168586  45280509  1732082741   66037462454 ...
7  | 28 1664 146642 11749134 889477656 66037462454 4872949974666 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..435
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Induced Subgraph

Rows 2..5 are A059020, A059021, A059524, A378940.
Main diagonal is A059525.
Cf. A116469, A140662, A286139, A286189, A292357, A378941.

A359574 Array read by antidiagonals: T(m,n) is the number of m X n binary arrays with all 1's connected and a path of 1's from top row to bottom row.

Original entry on oeis.org

1, 3, 1, 6, 7, 1, 10, 28, 17, 1, 15, 88, 144, 41, 1, 21, 245, 920, 730, 99, 1, 28, 639, 5191, 9362, 3692, 239, 1, 36, 1608, 27651, 104989, 94280, 18666, 577, 1, 45, 3968, 143342, 1111283, 2075271, 947760, 94384, 1393, 1, 55, 9689, 733512, 11457514, 42972329, 40792921, 9528128, 477264, 3363, 1

Offset: 1

Andrew Howroyd, Jan 06 2023

The grid has m rows and n columns.

			Array begins:
================================================================
m\n| 1   2     3       4         5           6             7
---+------------------------------------------------------------
1  | 1   3     6      10        15          21            28 ...
2  | 1   7    28      88       245         639          1608 ...
3  | 1  17   144     920      5191       27651        143342 ...
4  | 1  41   730    9362    104989     1111283      11457514 ...
5  | 1  99  3692   94280   2075271    42972329     866126030 ...
6  | 1 239 18666  947760  40792921  1642690309   64270256276 ...
7  | 1 577 94384 9528128 801218515 62618577481 4741764527414 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..435
Chaim Goodman-Strauss, Notes on the number of m × n binary arrays with all 1's connected and a path of 1's from top row to bottom row (May 21 2020)

Main diagonal is A163028.
Rows 1..10 are A000217, A163037, A163038, A163039, A163040, A163041, A163042, A163043, A163044, A163045.
Columns 1..10 are A000012, A001333(n+1), A163029, A163030, A163031, A163032, A163033, A163034, A163035, A163036.
Cf. A287151, A292357, A359573, A359576.

T(m,n) = A287151(m,n) - 2*A287151(m-1,n) + A287151(m-2,n) for m > 2.

A034184 Not necessarily symmetric n X 3 crossword puzzle grids.

Original entry on oeis.org

1, 15, 111, 649, 3495, 18189, 93231, 474479, 2406621, 12187137, 61668609, 311938233, 1577602849, 7977940187, 40342860995, 204001993697, 1031568839407, 5216271035257, 26376744398811, 133377264694375

Offset: 1

Erich Friedman

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Louis Marin, Counting Polyominoes in a Rectangle b X h, arXiv:2406.16413 [cs.DM], 2024. See p. 145.

Row 3 of A292357.
Column sums of A059679.
Cf. A001333, A034182, A034184, A034185, A034186, A034187.

Appears to obey a 9-term linear recurrence. - Ralf Stephan, May 05 2004

Empirical g.f.: -x*(x^8-x^7-2*x^6-9*x^5+14*x^4-11*x^3-6*x^2+5*x+1) / ((x-1)*(x^2+2*x-1)*(x^6-7*x^5+x^4+6*x^3-11*x^2+7*x-1)). - Colin Barker, Jun 09 2013

A034187 Not necessarily symmetric n X 4 crossword puzzle grids.

Original entry on oeis.org

1, 39, 649, 7943, 86995, 910667, 9339937, 94844591, 958363411, 9659847433, 97245624749, 978360244839, 9839915415611, 98949930968385, 994959069405031, 10004090931544495, 100586881489055547, 1011348141567934109

Offset: 1

Erich Friedman

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200

Row 4 of A292357.
Column sums of A059680.
Cf. A001333, A034184, A034185, A034186, A034187.

Empirical: a(n) = 24*a(n-1) - 218*a(n-2) + 1009*a(n-3) - 2623*a(n-4) + 3513*a(n-5) - 142*a(n-6) - 7707*a(n-7) + 11632*a(n-8) - 4443*a(n-9) - 6736*a(n-10) + 9655*a(n-11) - 3714*a(n-12) - 1529*a(n-13) + 1550*a(n-14) - 597*a(n-15) + 1041*a(n-16) + 195*a(n-17) - 150*a(n-18) + 8*a(n-19) + a(n-20) for n > 20. - Andrew Howroyd, Oct 02 2017

Empirical: x *(-1 -15*x +69*x^2 +140*x^3 -1117*x^4 +1696*x^5 +186*x^6 -1351*x^7 -1715*x^8 +3376*x^9 -52*x^10 -1829*x^11 +905*x^12 -1748*x^13 +446*x^14 -241*x^15 -72*x^16 +35*x^17 +7*x^18 +x^19) / ( (x^2+2*x-1) *(x^6 -7*x^5 +x^4 +6*x^3 -11*x^2 +7*x -1) *(x^12 +13*x^11 -71*x^10 +7*x^9 -113*x^8 +22*x^7 +222*x^6 -210*x^5 -19*x^4 +97*x^3 -59*x^2 +15*x -1) ). - R. J. Mathar, Jun 07 2020

A268371 Triangle read by rows: T(n,k) is the number of free polyominoes with width n and height 1<=k<=n.

Original entry on oeis.org

1, 1, 2, 1, 6, 24, 1, 12, 181, 1051, 1, 30, 941, 21992, 238048, 1, 65, 4662, 228013, 9735647, 195284973, 1, 158, 23691, 2337694, 195616247, 15256715219, 577169894573

Offset: 1

John Mason, Feb 03 2016

Superset of Craig Knecht's A268311.

			The first rows of the array are:
1;
1, 2;
1, 6, 24;
1, 12, 181, 1051;
...
T(4,3)=181 = 15+39+59+42+21+4+1: In the 4x3 square fit 15 6-ominoes, 39 7-ominoes, 59 8-ominoes, 42 9-ominoes, 21 10-ominoes, 4 11-ominoes or 1 12-omino. - _R. J. Mathar_, Jun 07 2020

Jean-Luc Manguin, Table of n, a(n) for n = 1..28
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).
Index entries for sequences related to polyominoes

Cf. A268311 (right diagonal), A335711 (column n=2), A000105 (free polyominoes), A292357 (equival. for fixed polys).

a(16)-a(28) from Jean-Luc Manguin, May 25 2020

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

A308359 Triangle T(n,w) read by rows: the number of fixed polyominoes with n cells and width w of the convex hull.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 9, 8, 1, 1, 18, 31, 12, 1, 1, 35, 95, 68, 16, 1, 1, 66, 269, 282, 121, 20, 1, 1, 123, 721, 1027, 638, 190, 24, 1, 1, 228, 1866, 3468, 2817, 1226, 275, 28, 1, 1, 421, 4728, 11132, 11254, 6391, 2110, 376, 32, 1, 1, 776, 11804, 34558, 42099, 29388, 12758, 3354, 493, 36, 1

Offset: 1

R. J. Mathar, May 22 2019

The sequence counts the fixed n-ominoes with prescribed bounding box width w and variable height w <= h <= n.

			T(3,2) = 4 counts the 4 variants of the L-shaped tromino rotated by multiples of 90 degrees. T(4,2) = 9 counts one O-tetromino in a 2 X 2 box, 4 L-tetrominoes in a 3 X 2 box, 2 T-tetromoes in a 3 X 2 box, and 2 Z-tetrominoes in a 3 X 2 box.
The triangle starts
  1;
  1,   1;
  1,   4,   1;
  1,   9,   8,   1;
  1,  18,  31,  12,   1;
  1,  35,  95,  68,  16,   1;
  1,  66, 269, 282, 121,  20,   1;

R. J. Mathar, Table of n, a(n) for n = 1..109
Index entries for sequences related to polyominoes

Cf. A027053 (column w=2), A335606 (w=3), A001168 (row sums), A273895, A292357 (prescribed w and h).

T(n,1) = T(n,n) = 1 (the straight n-ominoes).
T(n,n-1) = 4*n-8 for n >= 3 (width n-1 and height 2).
Conjecture: T(n,n-2) = 8*n^2 - 51*n + 86 for n >= 5.

A059681 Triangle T(n,k) giving number of fixed 5 X k polyominoes with n cells (n >= 5, 1<=k<=n-4).

Original entry on oeis.org

1, 0, 16, 0, 38, 83, 0, 32, 376, 230, 0, 10, 784, 1526, 497, 0, 1, 987, 5154, 4180, 932, 0, 0, 778, 11328, 18944, 9458, 1591, 0, 0, 370, 17598, 58665, 52488, 18936, 2538, 0, 0, 101, 19912, 135325, 204466, 123652, 34726, 3845, 0, 0, 15, 16440, 241550, 611859

Offset: 5

N. J. A. Sloane, Feb 05 2001

			Triangle starts:
1;
0, 16;
0, 38,  83;
0, 32, 376,   230;
0, 10, 784,  1526,   497;
0,  1, 987,  5154,  4180,  932;
0,  0, 778, 11328, 18944, 9458, 1591;
...

Andrew Howroyd, Table of n, a(n) for n = 5..1279
R. C. Read, Contributions to the cell growth problem, Canad. J. Math., 14 (1962), 1-20.

Column sums are row 5 of A292357.

Cf. A059678, A059679, A059680.

T(n,k) = 0 for n > 5*k. - Andrew Howroyd, Oct 02 2017

a(24) corrected and terms a(26) and beyond from Andrew Howroyd, Oct 02 2017

A232103 Square array read by antidiagonals: T(m,n) = number of ways of drawing a simple loop on an m x n rectangular lattice of dots in such a way that it touches each edge.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 15, 15, 1, 1, 39, 106, 39, 1, 1, 97, 582, 582, 97, 1, 1, 237, 2952, 6074, 2952, 237, 1, 1, 575, 14488, 56778, 56778, 14488, 575, 1, 1, 1391, 69982, 510600, 943340, 510600, 69982, 1391, 1, 1, 3361, 335356, 4502836, 15009212, 15009212

Offset: 1

Douglas Boffey, Nov 21 2013

This sequence is to be read as a table:
1,   1,   1,   1,   1, ...
1,   5,  15,  39, ...
1,  15, 106, ...
1,  39, ...
1, ...
...
This represents the number of simple, closed loops that can be formed on an m x n lattice of dots in such a way that it touches each edge.
This sequence is related to A231829, called b(i,j) by a(i,j) = b(i,j) - 2 * b(i,j-1) + b(i,j-2) - 2 * b(i-1,j) + 4 * b(i-1,j-1) - 2 * b(j-1,j-2) + b(i-2,j) - 2 * b(i-2,j-1) + b(i-2,j-2).
Equivalently, the number of fixed polyominoes without holes that have a width of m and height of n. - Andrew Howroyd, Oct 04 2017

			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   106     582      2952       14488        69982...
4  | 1  39   582    6074     56778      510600      4502836...
5  | 1  97  2952   56778    943340    15009212    234411981...
6  | 1 237 14488  510600  15009212   419355340  11509163051...
7  | 1 575 69982 4502836 234411981 11509163051 554485727288...
... - _Andrew Howroyd_, Oct 04 2017
a(3,2) is 15, thus:
1)        2)        3)        4)        5)
+-+-+-+   +-+-+-+   + +-+-+   +-+-+-+   +-+-+-+
|     |   |     |     |   |   |     |   |     |
+ +-+-+   +-+ +-+   +-+ +-+   + + +-+   +-+-+ +
| |         | |     |   |     |   |         | |
+-+ + +   + +-+ +   +-+-+ +   +-+-+ +   + + +-+
6)        7)        8)        9)        10)
+-+-+-+   +-+-+ +   +-+-+-+   +-+ + +   + +-+ +
|     |   |   |     |     |   | |         | |
+ +-+ +   +-+ +-+   +-+ + +   + +-+-+   +-+ +-+
| | | |     |   |     |   |   |     |   |     |
+-+ +-+   + +-+-+   + +-+-+   +-+-+-+   +-+-+-+
11)       12)       13)       14)       15)
+-+-+ +   + + +-+   +-+ +-+   + +-+-+   +-+-+-+
|   |         | |   | | | |     |   |   |     |
+   +-+   +-+-+ +   + +-+ +   +-+ + +   + + + +
|     |   |     |   |     |   |     |   |     |
+-+-+-+   +-+-+-+   +-+-+-+   +-+-+-+   +-+-+-+

Andrew Howroyd, Table of n, a(n) for n = 1..325
Jean-François Alcover, Mathematica program

Rows 2-3 are A034182, A293263.
Main diagonal is A293261.
Cf. A231829, A292357.

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) = A231829(m, n). - Andrew Howroyd, Oct 04 2017

cp's OEIS Frontend

A034182 Number of not-necessarily-symmetric n X 2 crossword puzzle grids.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A287151 Array read by antidiagonals: T(m,n) = number of nonzero m X n binary arrays with all 1's connected.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A359574 Array read by antidiagonals: T(m,n) is the number of m X n binary arrays with all 1's connected and a path of 1's from top row to bottom row.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A034184 Not necessarily symmetric n X 3 crossword puzzle grids.

Views

Author

Keywords

Links

Crossrefs

Formula

A034187 Not necessarily symmetric n X 4 crossword puzzle grids.

Views

Author

Keywords

Links

Crossrefs

Formula

A268371 Triangle read by rows: T(n,k) is the number of free polyominoes with width n and height 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A308359 Triangle T(n,w) read by rows: the number of fixed polyominoes with n cells and width w of the convex hull.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A059681 Triangle T(n,k) giving number of fixed 5 X k polyominoes with n cells (n >= 5, 1<=k<=n-4).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula