OFFSET
1,2
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.
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.
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.
EXAMPLE
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.
PROG
(Python) # See Rebenstock link.
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Jeremy Rebenstock and Thomas Ladouceur, Sep 24 2023
STATUS
approved