A359574 -id:A359574 - cp's OEIS frontend

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

1, 3, 1, 7, 7, 1, 15, 37, 17, 1, 31, 175, 197, 41, 1, 63, 781, 1985, 1041, 99, 1, 127, 3367, 18621, 22193, 5503, 239, 1, 255, 14197, 167337, 433809, 247759, 29089, 577, 1, 511, 58975, 1461797, 8057905, 10056959, 2764991, 153769, 1393, 1, 1023, 242461, 12519345, 144769425, 384479935, 232824241, 30856705, 812849, 3363, 1

Offset: 1

Andrew Howroyd, Jan 06 2023

The grid has m rows and n columns.
"Path" refers to a sequence of L(eft), R(ight), U(p), D(own) steps (edge connectivity like in fixed polyominoes), self-avoiding, starting anywhere in the first row and ending anywhere in the last row. The path does not need to step on all 1's of the array. The path has obviously at least m-1 steps. - R. J. Mathar, Jun 21 2023
Note that the total would be smaller if Up steps were disallowed (as in the original comment above); the smallest grid size for which this phenomenon occurs is 4 X 5. The total number of 4 X 5 and 5 X 5 grids would be 433801 instead of 433809 and 10056087 instead of 10056959, respectively, without Up steps. - Caleb Stanford, Feb 01 2024
Each row and each column satisfies a linear recurrence with constant coefficients. - Pontus von Brömssen, Feb 05 2025

			Array begins:
====================================================================
m\n| 1   2      3        4          5            6             7
---+----------------------------------------------------------------
1  | 1   3      7       15         31           63           127 ...
2  | 1   7     37      175        781         3367         14197 ...
3  | 1  17    197     1985      18621       167337       1461797 ...
4  | 1  41   1041    22193     433809      8057905     144769425 ...
5  | 1  99   5503   247759   10056959    384479935   14142942975 ...
6  | 1 239  29089  2764991  232824241  18287614751 1374273318721 ...
7  | 1 577 153769 30856705 5388274121 868972410929 ...
  ...
All the 37 2 X 3 binary arrays:
001 001 001 001
001 011 101 111 plus 4 copies left-right flipped
.
010 010 010 010
010 011 110 111
.
011 011 011 011 011 011
001 010 011 101 110 111 plus 6 copies left-right flipped
.
101 101 101 101 101 101
001 011 100 101 110 111
.
111 111 111 111 111 111 111
001 010 011 100 101 110 111 - _R. J. Mathar_, Jun 21 2023

Samuel Dittmer, Hiram Golze, Grant Molnar, and Caleb Stanford, Puzzle and Proof: A Decade of Problems from the Utah Math Olympiad, CRC Press, 2025, p. 51.

Caleb Stanford, Rust program to compute the sequence.
Utah Math Olympiad 2022, Problem 6.

Main diagonal is A365988.
Rows 1..19 are A000225, A005061, A069361, A069362, A069363-A069377.
Columns 1..20 are A000012, A001333(n+1), A069378, A069379, A069380-A069395.
Cf. A359574, A359575.

One additional diagonal of terms added by Caleb Stanford, Feb 05 2024

A359573 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 upper left corner to lower right corner.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 8, 8, 1, 1, 20, 45, 20, 1, 1, 49, 234, 234, 49, 1, 1, 119, 1193, 2423, 1193, 119, 1, 1, 288, 6049, 24455, 24455, 6049, 288, 1, 1, 696, 30616, 245972, 482443, 245972, 30616, 696, 1, 1, 1681, 154861, 2473317, 9469361, 9469361, 2473317, 154861, 1681, 1

Offset: 1

Andrew Howroyd, Jan 06 2023

			Array begins:
================================================================
m\n| 1   2     3       4         5           6             7
---+------------------------------------------------------------
1  | 1   1     1       1         1           1             1 ...
2  | 1   3     8      20        49         119           288 ...
3  | 1   8    45     234      1193        6049         30616 ...
4  | 1  20   234    2423     24455      245972       2473317 ...
5  | 1  49  1193   24455    482443     9469361     185899132 ...
6  | 1 119  6049  245972   9469361   360923899   13742823032 ...
7  | 1 288 30616 2473317 185899132 13742823032 1012326365581 ...
  ...

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

Main diagonal is A163002.
Rows 1..10 are A000012, A048739(n-1), A163003, A163004, A163005, A163006, A163007, A163008, A163009, A163010.
Cf. A287151, A359574, A359575, A359576.

T(m,n) = T(n,m).

A163028 Number of n X n binary arrays with all 1s connected and a path of 1s from the top row to the bottom row.

Original entry on oeis.org

1, 7, 144, 9362, 2075271, 1642690309, 4741764527414, 50301538415794232, 1966097907322824101263, 283293243539676951470723543, 150432229851691149674511947484546, 294212923045987478712868787193615243838, 2117957004814862762696618942898524645283531305

Offset: 1

R. H. Hardin, Jul 20 2009

nonn

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

Main diagonal of A359574.

Terms a(8) and beyond from Andrew Howroyd, Jan 06 2023

A163031 Number of n X 5 binary arrays with all 1s connected and a path of 1s from top row to bottom row.

Original entry on oeis.org

15, 245, 5191, 104989, 2075271, 40792921, 801218515, 15736428305, 309080891641, 6070750256417, 119237718452471, 2341990743046197, 45999883370408813, 903500281246849523, 17745974522766912147, 348555078644003475079

Offset: 1

R. H. Hardin, Jul 20 2009

nonn

R. H. Hardin, Table of n, a(n) for n=1..21
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)
Chaim Goodman-Strauss, Mma notebook to accompany the above document

Column 5 of A359574.

Cf. A163029-A163036.

For a formula see the Goodman-Strauss links. - N. J. A. Sloane, May 22 2020

A163032 Number of n X 6 binary arrays with all 1s connected and a path of 1s from top row to bottom row.

Original entry on oeis.org

21, 639, 27651, 1111283, 42972329, 1642690309, 62618577481, 2385542862643, 90870669971589, 3461426734215747, 131852221160935917, 5022507165784282263, 191317198008071782069, 7287650933960562176059, 277601073047629123048799, 10574375404737019213183521

Offset: 1

R. H. Hardin, Jul 20 2009

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
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)
Chaim Goodman-Strauss, Mma notebook to accompany the above document

Column 6 of A359574.

Cf. A163029-A163036.

For a formula see the Goodman-Strauss links. - N. J. A. Sloane, May 22 2020

Terms a(11) and beyond from Andrew Howroyd, Jan 06 2023

A163033 Number of n X 7 binary arrays with all 1s connected and a path of 1s from top row to bottom row.

Original entry on oeis.org

28, 1608, 143342, 11457514, 866126030, 64270256276, 4741764527414, 349218174915782, 25705066468491048, 1891784307926020004, 139221054649194353330, 10245491277444041078478, 753978851322477798813560, 55486218768479949691575070, 4083297106688472106576343018

Offset: 1

R. H. Hardin, Jul 20 2009

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
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)
Chaim Goodman-Strauss, Mma notebook to accompany the above document

Column 7 of A359574.

Cf. A163029-A163036.

For a formula see the Goodman-Strauss links. - N. J. A. Sloane, May 22 2020

Terms a(9) and beyond from Andrew Howroyd, Jan 06 2023

A163034 Number of n X 8 binary arrays with all 1s connected and a path of 1s from top row to bottom row.

Original entry on oeis.org

36, 3968, 733512, 116648336, 17234589848, 2481063626002, 353883736096148, 50301538415794232, 7140496309756236272, 1013108119964866470278, 143713897214120554999482, 20384925139787491684594856, 2891390846534568194577474354, 410109224260079991594244323232

Offset: 1

R. H. Hardin, Jul 20 2009

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
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)
Chaim Goodman-Strauss, Mma notebook to accompany the above document

Column 8 of A359574.

Cf. A163029-A163036.

For a formula see the Goodman-Strauss links. - N. J. A. Sloane, May 22 2020

Terms a(8) and beyond from Andrew Howroyd, Jan 06 2023

A163040 Number of n X 5 binary arrays with all 1s connected and a path of 1s from left column to right column.

Original entry on oeis.org

1, 99, 3692, 94280, 2075271, 42972329, 866126030, 17234589848, 340759985173, 6715679348165, 132133640829902, 2597584688864178, 51043234543210529, 1002791241847545847, 19698523732748736840, 386929326073777902750, 7600054817584231361621, 149277792786859197467919

Offset: 1

R. H. Hardin, Jul 20 2009

nonn

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

Row 5 of A359574.

Terms a(14) and beyond from Andrew Howroyd, Jan 06 2023

A163041 Number of n X 6 binary arrays with all 1s connected and a path of 1s from left column to right column.

Original entry on oeis.org

1, 239, 18666, 947760, 40792921, 1642690309, 64270256276, 2481063626002, 95151328370775, 3637116511064523, 138792924786810014, 5291772896345008640, 201669960952305135745, 7683892181372221416041, 292731696495415484045432, 11151457805393688893262636

Offset: 1

R. H. Hardin, Jul 20 2009

nonn

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

Row 6 of A359574.

Terms a(11) and beyond from Andrew Howroyd, Jan 06 2023

A163042 Number of n X 7 binary arrays with all 1s connected and a path of 1s from left column to right column.

Original entry on oeis.org

1, 577, 94384, 9528128, 801218515, 62618577481, 4741764527414, 353883736096148, 26226659917104393, 1936966961305957565, 142805176707285744704, 10519121991556481091992, 774491701732750702097515, 57010108651586254737175513, 4195987647889791129869411078

Offset: 1

R. H. Hardin, Jul 20 2009

nonn

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

Row 7 of A359574.

Terms a(9) and beyond from Andrew Howroyd, Jan 06 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A359573 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 upper left corner to lower right corner.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A163028 Number of n X n binary arrays with all 1s connected and a path of 1s from the top row to the bottom row.

Views

Author

Keywords

Links

Crossrefs

Extensions

A163031 Number of n X 5 binary arrays with all 1s connected and a path of 1s from top row to bottom row.

Views

Author

Keywords

Links

Crossrefs

Formula

A163032 Number of n X 6 binary arrays with all 1s connected and a path of 1s from top row to bottom row.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A163033 Number of n X 7 binary arrays with all 1s connected and a path of 1s from top row to bottom row.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A163034 Number of n X 8 binary arrays with all 1s connected and a path of 1s from top row to bottom row.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A163040 Number of n X 5 binary arrays with all 1s connected and a path of 1s from left column to right column.

Views

Author

Keywords

Links

Crossrefs

Extensions

A163041 Number of n X 6 binary arrays with all 1s connected and a path of 1s from left column to right column.

Views

Author

Keywords

Links

Crossrefs

Extensions

A163042 Number of n X 7 binary arrays with all 1s connected and a path of 1s from left column to right column.

Views

Author

Keywords

Links

Crossrefs

Extensions