A340043 Triangle T(n,k), n>=1, 0 <= k <= A002620(n-1), read by rows, where T(n,k) is the number of self-avoiding paths of length 2*(n+k) along the edges of a grid with n X n square cells, which do not pass above the diagonal, start at the lower left corner and finish at the upper right corner.

1, 2, 5, 2, 14, 16, 10, 42, 90, 123, 94, 20, 132, 440, 954, 1460, 1524, 922, 248, 429, 2002, 6017, 13688, 24582, 34536, 35487, 24042, 8852, 1072, 1430, 8736, 33784, 101232, 251646, 530900, 944042, 1369110, 1541774, 1264402, 693740, 221738, 31178

Offset

1,2

Links

Siqi Wang, Rows n = 1..24, flattened (rows 1..14 from Seiichi Manyama).

Siqi Wang, C++ program used to generate the sequence.

Example

Triangle begins:
    1;
    2;
    5,    2;
   14,   16,   10;
   42,   90,  123,    94,    20;
  132,  440,  954,  1460,  1524,   922,   248;
  429, 2002, 6017, 13688, 24582, 34536, 35487, 24042, 8852, 1072;

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 A340043(n):
    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(2 * (n + k)).len() for k in range((n - 1) * (n - 1) // 4 + 1)]
print([i for n in range(1, 9) for i in A340043(n)])

Crossrefs

Column 0 gives A000108.

Row sum gives A340005.

Cf. A002620.

Sequence in context: A102469 A098886 A286785 * A257514 A089120 A286452

Adjacent sequences: A340040 A340041 A340042 * A340044 A340045 A340046

Keyword

nonn,tabf

Author

Seiichi Manyama, Dec 26 2020

Status

approved