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.

1, 1, 2, 7, 40, 369, 5680, 150707, 6993712, 567670347, 80294818098, 19750798800833, 8447500756620198, 6286515496550185699, 8145835634791919637646, 18387066260739625200447575, 72319765957232441125506763756, 495718308213370458738098777141317

Offset

0,3

Links

Siqi Wang, Table of n, a(n) for n = 0..31

Example

3 X 3 square cells
  *---*---*---E
  |   |   |   |
  *---*---*---*
  |   |   |   |
  *---*---*---*
  |   |   |   |
  S---*---*---*
a(3) = A000108(3) + 2 = 7;
              E              E              E
              |              |              |
              *              *          *---*
              |              |          |
              *      *---*---*      *---*
              |      |              |
  S---*---*---*  S---*          S---*
              E              E
              |              |
              *          *---*
              |          |
          *---*          *
          |              |
  S---*---*      S---*---*
              E              E
              |              |
              *          *---*
              |          |
      *---*   *          *---*
      |   |   |              |
  S---*   *---*  S---*---*---*

Prog

(Python)
# Using graphillion
from graphillion import GraphSet
def make_stairs(n):
    s = 1
    grids = []
    for i in range(n + 1, 1, -1):
        for j in range(i - 1):
            a, b, c = s + j, s + j + 1, s + i + j
            grids.extend([(a, b), (a, c)])
        s += i
    return grids
def A340005(n):
    if n == 0: return 1
    universe = make_stairs(n)
    GraphSet.set_universe(universe)
    start, goal = n + 1, (n + 1) * (n + 2) // 2
    paths = GraphSet.paths(start, goal)
    return paths.len()
print([A340005(n) for n in range(15)])

Crossrefs

Row sum of A340043.

Cf. A000108, A007764.

Sequence in context: A006455 A130715 A317723 * A325061 A358745 A215207

Adjacent sequences: A340002 A340003 A340004 * A340006 A340007 A340008

Keyword

nonn

Author

Seiichi Manyama, Dec 26 2020

Status

approved