|
%I #29 Jun 18 2022 18:54:52
%S 1,1,2,7,40,369,5680,150707,6993712,567670347,80294818098,
%T 19750798800833,8447500756620198,6286515496550185699,
%U 8145835634791919637646,18387066260739625200447575,72319765957232441125506763756,495718308213370458738098777141317
%N Number of self-avoiding paths along the edges of a grid with n X n square cells, which do not pass above the diagonal. The paths start at the lower left corner and finish at the upper right corner.
%H Siqi Wang, <a href="/A340005/b340005.txt">Table of n, a(n) for n = 0..31</a>
%e 3 X 3 square cells
%e *---*---*---E
%e | | | |
%e *---*---*---*
%e | | | |
%e *---*---*---*
%e | | | |
%e S---*---*---*
%e a(3) = A000108(3) + 2 = 7;
%e E E E
%e | | |
%e * * *---*
%e | | |
%e * *---*---* *---*
%e | | |
%e S---*---*---* S---* S---*
%e E E
%e | |
%e * *---*
%e | |
%e *---* *
%e | |
%e S---*---* S---*---*
%e E E
%e | |
%e * *---*
%e | |
%e *---* * *---*
%e | | | |
%e S---* *---* S---*---*---*
%o (Python)
%o # Using graphillion
%o from graphillion import GraphSet
%o def make_stairs(n):
%o s = 1
%o grids = []
%o for i in range(n + 1, 1, -1):
%o for j in range(i - 1):
%o a, b, c = s + j, s + j + 1, s + i + j
%o grids.extend([(a, b), (a, c)])
%o s += i
%o return grids
%o def A340005(n):
%o if n == 0: return 1
%o universe = make_stairs(n)
%o GraphSet.set_universe(universe)
%o start, goal = n + 1, (n + 1) * (n + 2) // 2
%o paths = GraphSet.paths(start, goal)
%o return paths.len()
%o print([A340005(n) for n in range(15)])
%Y Row sum of A340043.
%Y Cf. A000108, A007764.
%K nonn
%O 0,3
%A _Seiichi Manyama_, Dec 26 2020
| 