

A365988


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


2



1, 7, 197, 22193, 10056959, 18287614751, 133267613878665, 3888492110032890000, 454016084146596000000000, 212041997127527000000000000000, 396017759826921000000000000000000000
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



FORMULA

Upper limit: a(n) <= 2^(n^2). This is the total number of boards possible.
Lower limit: a(n) >= 2^(n1)*a(n1) 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 17 since there is a path to the top from the bottom. So a(2) = 7.


PROG

(Python) see link


CROSSREFS



KEYWORD

nonn,walk


AUTHOR



STATUS

approved



