cp's OEIS Frontend

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

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