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

Author

Jeremy Rebenstock and Thomas Ladouceur, Sep 24 2023

Keywords

• nonn
• walk

Comments

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.

Examples

			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.
		

References

• 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.

Links

• 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.

Crossrefs

Main diagonal of A359576.

Cf. A069343, A163028.

Programs

Python

# See Rebenstock link.

Formula

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.