A333509 Square array T(n,k), n >= 1, k >= 2, read by antidiagonals, where T(n,k) is the number of self-avoiding walks in the n X k grid graph which start at any of the n vertices on left side of the graph and terminate at any of the n vertices on the right side.

1, 1, 8, 1, 16, 29, 1, 32, 95, 80, 1, 64, 313, 426, 195, 1, 128, 1033, 2320, 1745, 444, 1, 256, 3411, 12706, 16347, 6838, 969, 1, 512, 11265, 69662, 154259, 112572, 25897, 2056, 1, 1024, 37205, 381964, 1454495, 1859660, 752245, 95292, 4279

Offset: 1

Author

Seiichi Manyama, Mar 25 2020

Keywords

• nonn
• tabl

Examples

			Square array T(n,k) begins:
    1,    1,      1,       1,        1, ...
    8,   16,     32,      64,      128, ...
   29,   95,    313,    1033,     3411, ...
   80,  426,   2320,   12706,    69662, ...
  195, 1745,  16347,  154259,  1454495, ...
  444, 6838, 112572, 1859660, 30549774, ...
		

Crossrefs

Columns k=2-3 give: A333510, A333511.

Rows n=1-3 give: A000012, A000079(n+1), 2*A082574(n+1)+1.

T(n,n) gives A121785(n-1).

Programs

Python

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A(start, goal, n, k):
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    paths = GraphSet.paths(start, goal)
    return paths.len()
def A333509(n, k):
    if n == 1: return 1
    s = 0
    for i in range(1, n + 1):
        for j in range(k * n - n + 1, k * n + 1):
            s += A(i, j, k, n)
    return s
print([A333509(j + 1, i - j + 2) for i in range(9) for j in range(i + 1)])