A359576 -id:A359576 - cp's OEIS frontend

A365988 Number of n X n binary arrays with a path of adjacent 1's from top row to bottom row.

1, 7, 197, 22193, 10056959, 18287614751, 133267613878665, 3888492110032890000, 454016084146596000000000, 212041997127527000000000000000, 396017759826921000000000000000000000

Offset: 1

Jeremy Rebenstock and Thomas Ladouceur, Sep 24 2023

a(n) is the number of climbable arrangements that exist for sets of n adjacent "broken ladders" with height n, where a broken ladder is an array of n steps with some number of the steps unusable, the rest usable; an arrangement is the configuration of the locations of the broken rung(s) on the n ladders of height n; and a climbable arrangement is a set of ladders such that with movement up, down, left, and right, there exists a path from the bottom to the top.

Also, a(n) is the sum of the coefficients of exact spanning probabilities in 2d lattices along the second dimension for an n X n square lattice.

			x indicates a broken rung, - a functional rung.
.
  |-| |-|        |x| |-|        |-| |x|        |-| |-|
  |-| |-| (1)    |-| |-| (2)    |-| |-| (3)    |-| |x| (4)
.
  |-| |-|        |x| |-|        |-| |x|        |-| |-|
  |x| |-| (5)    |x| |-| (6)    |-| |x| (7)    |x| |x| (8)
.
  |x| |x|        |x| |-|        |-| |x|        |x| |x|
  |-| |-| (9)    |-| |x| (10)   |x| |-| (11)   |-| |x| (12)
.
  |x| |x|        |x| |-|        |-| |x|        |x| |x|
  |x| |-| (13)   |x| |x| (14)   |x| |x| (15)   |x| |x| (16)
.
The only climbable configurations are 1-7 since there is a path to the top from the bottom. So a(2) = 7.

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.

Stephan Mertens, Percolation.
Jeremy Rebenstock, Python notebook for calculating and visualizing a(n).
Jeremy Rebenstock and Thomas Ladouceur, Illustration for a(2) = 7.
R. M. Ziff and M. E. J. Newman, Convergence of threshold estimates for two-dimensional percolation, arXiv:cond-mat/0203496 [cond-mat.stat-mech], 2002.

Main diagonal of A359576.

Cf. A069343, A163028.

Python
```
# See Rebenstock link.
```

Upper limit: a(n) <= 2^(n^2). This is the total number of boards possible.

Lower limit: a(n) >= 2^(n-1)*a(n-1) climbable paths (board before it, with a completely unbroken ladder) and we break any arrangement of rungs on the new ladder.

A069363 Number of 5 X n binary arrays with a path of adjacent 1's from top row to bottom row.

Original entry on oeis.org

1, 99, 5503, 247759, 10056959, 384479935, 14142942975, 506544513343, 17792504911231, 615793150236223, 21067276157958271, 714097521397778495, 24022705580163949439, 803089367467759614015, 26706726258154287563903

Offset: 1

R. H. Hardin, Mar 22 2002

nonn

Row 5 of A359576.

Cf. 1 X n A000225, 2 X n A005061, n X 2 A001333, vertical path of 1 A069361-A069395, vertical paths of 0+1 A069396-A069416, vertical path of 1 not 0 A069417-A069428, no vertical paths A069429-A069447, no horizontal or vertical paths A069448-A069452.

A368809 Number of 4 X n binary arrays with a path of adjacent 1's from top row to bottom row using only left, right, and downward steps.

Original entry on oeis.org

1, 41, 1041, 22193, 433801, 8057625, 144762849, 2540882465, 43840779353, 746649798473, 12587443678705, 210491254232465, 3496816762316713, 57778098654714361, 950391251581267073, 15574198350636963201, 254405750326548970361, 4144508602760970898729, 67361936661916258817937

Offset: 1

Caleb Stanford, Feb 05 2024

Unlike A069362, does not allow upward steps.

			For example, here is one such 4 X 4 array:
    0001
    1111
    1010
    1100
The following 4 X 5 array is a non-example, as there is no path using only left, right, and downward steps:
    10000
    10111
    11101
    00001

Index entries for linear recurrences with constant coefficients, signature (36,-413,1642,-2536,1152).

Row 4 of A369892.

Cf. A069362, A359576.

G.f.: x*(1 + 5*x - 22*x^2 + 8*x^3)/((1 - 16*x)*(1 - 20*x + 93*x^2 - 154*x^3 + 72*x^4)). - Pontus von Brömssen, Feb 05 2025

More terms from Pontus von Brömssen, Feb 05 2025

A369892 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 using only left, right, and downward steps.

Original entry on oeis.org

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, 433801, 247759, 29089, 577, 1, 511, 58975, 1461797, 8057625, 10056087, 2764991, 153769, 1393, 1, 1023, 242461, 12519345, 144762849, 384409519, 232777209, 30856705, 812849, 3363, 1

Offset: 1

Caleb Stanford, Feb 05 2024

Similar to A359576 but disallowing Up steps.
The sequences are initially similar but differ for 4 X 5 grids (433801 instead of 433809), 4 X 6 grids (8057625 instead of 8057905), and 5 X 5 grids (10056087 instead of 10056959)
Can be calculated by dynamic programming from 1 X n grids to m X n grids by keeping track of the number of grids with each of the 2^n patterns of reachable squares in the last row.
Each row and each column satisfies a linear recurrence with constant coefficients. - Pontus von Brömssen, Feb 05 2025

			For the 37 2 X 3 grids, see A359576.
The following 4 X 5 grid is a counterexample that is counted by A359576 but not by the present sequence:
    10000
    10111
    11101
    00001
Notice that there is a path of 1s from the top to the bottom, but only via the upward step detour in the third column. There are 8 such 4 X 5 grids, formed from the above by reflection and by toggling the first row, second column and last row, second to last column.
Table starts:
    1      3        7         15          31          63         127 ...
    1      7       37        175         781        3367       14197 ...
    1     17      197       1985       18621      167337     1461797 ...
    1     41     1041      22193      433801     8057625   144762849 ...
    1     99     5503     247759    10056087   384409519   ...
    1    239    29089    2764991   232777209   ...
    1    577   153769   30856705   ...
    1   1393   812849   ...
    1   3363   ...
    1   ...
    ...

Caleb Stanford, Rust program to compute the sequence.

First 4 rows are A000225, A005061, A069361, A368809.
First 4 columns are A000012, A001333, A069378, A069379.
Cf. A359576 (up steps allowed).

cp's OEIS Frontend

A365988 Number of n 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

Programs

Python

Formula

A069363 Number of 5 X n binary arrays with a path of adjacent 1's from top row to bottom row.

Views

Author

Keywords

Crossrefs

A368809 Number of 4 X n binary arrays with a path of adjacent 1's from top row to bottom row using only left, right, and downward steps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A369892 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 using only left, right, and downward steps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs