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

Links

Table of n, a(n) for n=1..11.

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 link

Crossrefs

Main diagonal of A359576.

Cf. A069343, A163028.

Sequence in context: A041371 A136675 A099198 * A058391 A157388 A068233

Adjacent sequences: A365985 A365986 A365987 * A365989 A365990 A365991

Keyword

nonn,walk

Author

Jeremy Rebenstock and Thomas Ladouceur, Sep 24 2023

Status

approved