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.

%I A365988 #52 Jan 24 2025 08:41:35
%S A365988 1,7,197,22193,10056959,18287614751,133267613878665,
%T A365988 3888492110032890000,454016084146596000000000,
%U A365988 212041997127527000000000000000,396017759826921000000000000000000000
%N A365988 Number of n X n binary arrays with a path of adjacent 1's from top row to bottom row.
%C A365988 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.
%C A365988 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.
%D A365988 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.
%H A365988 Stephan Mertens, <a href="https://wasd.urz.uni-magdeburg.de/mertens/research/percolation/">Percolation</a>.
%H A365988 Jeremy Rebenstock, <a href="/A365988/a365988.ipynb.txt">Python notebook for calculating and visualizing a(n)</a>.
%H A365988 Jeremy Rebenstock and Thomas Ladouceur, <a href="/A365988/a365988.png">Illustration for a(2) = 7</a>.
%H A365988 R. M. Ziff and M. E. J. Newman, <a href="https://arxiv.org/abs/cond-mat/0203496">Convergence of threshold estimates for two-dimensional percolation</a>, arXiv:cond-mat/0203496 [cond-mat.stat-mech], 2002.
%F A365988 Upper limit: a(n) <= 2^(n^2). This is the total number of boards possible.
%F A365988 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.
%e A365988 x indicates a broken rung, - a functional rung.
%e A365988 .
%e A365988   |-| |-|        |x| |-|        |-| |x|        |-| |-|
%e A365988   |-| |-| (1)    |-| |-| (2)    |-| |-| (3)    |-| |x| (4)
%e A365988 .
%e A365988   |-| |-|        |x| |-|        |-| |x|        |-| |-|
%e A365988   |x| |-| (5)    |x| |-| (6)    |-| |x| (7)    |x| |x| (8)
%e A365988 .
%e A365988   |x| |x|        |x| |-|        |-| |x|        |x| |x|
%e A365988   |-| |-| (9)    |-| |x| (10)   |x| |-| (11)   |-| |x| (12)
%e A365988 .
%e A365988   |x| |x|        |x| |-|        |-| |x|        |x| |x|
%e A365988   |x| |-| (13)   |x| |x| (14)   |x| |x| (15)   |x| |x| (16)
%e A365988 .
%e A365988 The only climbable configurations are 1-7 since there is a path to the top from the bottom. So a(2) = 7.
%o A365988 (Python) # See Rebenstock link.
%Y A365988 Main diagonal of A359576.
%Y A365988 Cf. A069343, A163028.
%K A365988 nonn,walk
%O A365988 1,2
%A A365988 _Jeremy Rebenstock_ and _Thomas Ladouceur_, Sep 24 2023