A333511 Number of self-avoiding walks in the n X 3 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, 16, 95, 426, 1745, 6838, 25897, 95292, 342505, 1208392, 4201765, 14445130, 49221691, 166563454, 560595853, 1878809676, 6275993883, 20910561068

Offset: 1

Author

Seiichi Manyama, Mar 25 2020

Keywords

• nonn

Examples

			a(1) = 1;
   +--*--+
a(2) = 16;
   +  *--+   +  *  +   +--*  +   +--*--+
   |  |      |     |      |  |
   *--*  *   *--*--*   *  *--*   *  *  *
   -------------------------------------
   +  *--*   +  *  *   +--*  *   +--*--*
   |  |  |   |            |            |
   *--*  +   *--*--+   *  *--+   *  *  +
   -------------------------------------
   *--*  +   *--*--+   *  *--+   *  *  +
   |  |  |   |            |            |
   +  *--*   +  *  *   +--*  *   +--*--*
   -------------------------------------
   *--*  *   *--*--*   *  *--*   *  *  *
   |  |      |     |      |  |
   +  *--+   +  *  +   +--*  +   +--*--+
		

Crossrefs

Column k=3 of A333509.

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
def A333511(n):
    return A333509(n, 3)
print([A333511(n) for n in range(1, 15)])