A163028 -id:A163028 - 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.

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

Original entry on oeis.org

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.

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