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,3

Links

Table of n, a(n) for n=1..45.

Example

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

Prog

(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)])

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

Sequence in context: A317026 A126000 A326992 * A013615 A359628 A369404

Adjacent sequences: A333506 A333507 A333508 * A333510 A333511 A333512

Keyword

nonn,tabl

Author

Seiichi Manyama, Mar 25 2020

Status

approved