A163036 -id:A163036 - cp's OEIS frontend

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.

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.

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

Original entry on oeis.org

6, 28, 144, 730, 3692, 18666, 94384, 477264, 2413346, 12203374, 61707810, 312032874, 1577831334, 7978491800, 40344192708, 204005208738, 1031576601204, 5216289773894, 26376789637884, 133377373911160, 674438554337506

Offset: 1

R. H. Hardin, Jul 20 2009

nonn

R. H. Hardin, Table of n, a(n) for n = 1..100
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

Cf. A001333 ((n-1) X 2 arrays), A059021 (no path required).

Cf. also A163030, A163031, A163032, A163033, A163034, A163035, A163036.

a(n) = 7*a(n-1) - 11*a(n-2) + 6*a(n-3) + a(n-4) - 7*a(n-5) + a(n-6). [Conjectured by R. J. Mathar, Aug 11 2009]
Proof from Peter Kagey, May 08 2019: Scanning from top to bottom, there are 6 possible intermediate states that the bottom row can be in. The transitions between these states define a 6 X 6 transition matrix whose characteristic polynomial agrees with the characteristic polynomial of the above recurrence. QED
For an alternative proof see the Goodman-Strauss links. - N. J. A. Sloane, May 22 2020

A163030 Number of nX4 binary arrays with all 1s connected and a path of 1s from top row to bottom row.

Original entry on oeis.org

10, 88, 920, 9362, 94280, 947760, 9528128, 95797726, 963186740, 9684246062, 97369020768, 978984263266, 9843070964036, 98965887676178, 995039757124590, 10004498940354450, 100588944638377056, 1011358574138112578

Offset: 1

R. H. Hardin Jul 20 2009

nonn

R. H. Hardin, Table of n, a(n) for n=1..44
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

Cf. A163029-A163036.

Empirical: a(n)= 15*a(n-1) -59*a(n-2) +97*a(n-3) -19*a(n-4) -210*a(n-5) +222*a(n-6) +22*a(n-7) -113*a(n-8) +7*a(n-9) -71*a(n-10) +13*a(n-11) +a(n-12). [From R. J. Mathar, Aug 11 2009]

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

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

A163035 Number of nX9 binary arrays with all 1s connected and a path of 1s from top row to bottom row.

Original entry on oeis.org

45, 9689, 3730303, 1180202569, 340759985173, 95151328370775

Offset: 1

R. H. Hardin Jul 20 2009

nonn

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

Cf. A163029-A163036.

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

cp's OEIS Frontend

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

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

Views

Author

Keywords

Links

Crossrefs

Formula

A163030 Number of nX4 binary arrays with all 1s connected and a path of 1s from top row to bottom row.

Views

Author

Keywords

Links

Crossrefs

Formula

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

A163035 Number of nX9 binary arrays with all 1s connected and a path of 1s from top row to bottom row.

Views

Author

Keywords

Links

Crossrefs

Formula