A333510 Number of self-avoiding walks in the n X 2 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, 8, 29, 80, 195, 444, 969, 2056, 4279, 8788, 17885, 36176, 72875, 146412, 293649, 588312, 1177855, 2357188, 4716133, 9434336, 18871091, 37744988, 75493209, 150990120, 301984455, 603973684, 1207952749, 2415911536, 4831829819, 9663667148, 19327342625, 38654694456, 77309399055, 154618809252

Offset: 1

Author

Seiichi Manyama, Mar 25 2020

Keywords

• nonn

Examples

			a(1) = 1;
   +--+
a(2) = 8;
   +--+   +  +   +--*   +  *
          |  |      |   |
   *  *   *--*   *  +   *--+
   -------------------------
   *--+   *  +   *--*   *  *
   |         |   |  |
   +  *   +--*   +  +   +--+
a(3) = 29;
   +--+   +  +   +  +   +--*   +  *
          |  |   |  |      |   |
   *  *   *--*   *  *   *  +   *--+
                 |  |
   *  *   *  *   *--*   *  *   *  *
   --------------------------------
   +  *   +--*   +--*   +  *   +  *
   |         |      |   |      |
   *  +   *--*   *  *   *--*   *  *
   |  |   |         |      |   |
   *--*   *--+   *  +   *  +   *--+
   --------------------------------
   *--+   *  +   *  +   *--*   *  *
   |         |      |   |  |
   +  *   +--*   +  *   +  +   +--+
                 |  |
   *  *   *  *   *--+   *  *   *  *
   --------------------------------
   *  *   *--*   *  *   *  *   *--+
          |  |                 |
   +  +   +  *   +--*   +  *   *--*
   |  |      |      |   |         |
   *--*   *  +   *  +   *--+   +--*
   --------------------------------
   *--+   *  +   *  +   *--*   *  *
   |         |      |   |  |
   *  *   *--*   *  *   *  +   *--+
   |      |         |   |      |
   +  *   +  *   +--*   +  *   +  *
   --------------------------------
   *  *   *--*   *  *   *  *
          |  |
   *  +   *  *   *--*   *  *
      |   |  |   |  |
   +--*   +  +   +  +   +--+
		

Crossrefs

Column k=2 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 A333510(n):
    return A333509(n, 2)
print([A333510(n) for n in range(1, 20)])

Formula

Conjecture: a(n) = (27*2^n - n^3 - 26*n - 24)/3.

Conjecture: G.f.: x*(1+2*x-5*x^2+2*x^3+2*x^4)/((1-x)^4*(1-2*x)).