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

Links

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

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

Example

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

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

Crossrefs

Column k=2 of A333509.

Sequence in context: A290312 A028419 A046664 * A055536 A131438 A048478

Adjacent sequences: A333507 A333508 A333509 * A333511 A333512 A333513

Keyword

nonn

Author

Seiichi Manyama, Mar 25 2020

Status

approved