cp's OEIS Frontend

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.

%I A333510 #29 Mar 26 2020 07:12:05
%S A333510 1,8,29,80,195,444,969,2056,4279,8788,17885,36176,72875,146412,293649,
%T A333510 588312,1177855,2357188,4716133,9434336,18871091,37744988,75493209,
%U A333510 150990120,301984455,603973684,1207952749,2415911536,4831829819,9663667148,19327342625,38654694456,77309399055,154618809252
%N 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.
%F A333510 Conjecture: a(n) = (27*2^n - n^3 - 26*n - 24)/3.
%F A333510 Conjecture: G.f.: x*(1+2*x-5*x^2+2*x^3+2*x^4)/((1-x)^4*(1-2*x)).
%e A333510 a(1) = 1;
%e A333510    +--+
%e A333510 a(2) = 8;
%e A333510    +--+   +  +   +--*   +  *
%e A333510           |  |      |   |
%e A333510    *  *   *--*   *  +   *--+
%e A333510    -------------------------
%e A333510    *--+   *  +   *--*   *  *
%e A333510    |         |   |  |
%e A333510    +  *   +--*   +  +   +--+
%e A333510 a(3) = 29;
%e A333510    +--+   +  +   +  +   +--*   +  *
%e A333510           |  |   |  |      |   |
%e A333510    *  *   *--*   *  *   *  +   *--+
%e A333510                  |  |
%e A333510    *  *   *  *   *--*   *  *   *  *
%e A333510    --------------------------------
%e A333510    +  *   +--*   +--*   +  *   +  *
%e A333510    |         |      |   |      |
%e A333510    *  +   *--*   *  *   *--*   *  *
%e A333510    |  |   |         |      |   |
%e A333510    *--*   *--+   *  +   *  +   *--+
%e A333510    --------------------------------
%e A333510    *--+   *  +   *  +   *--*   *  *
%e A333510    |         |      |   |  |
%e A333510    +  *   +--*   +  *   +  +   +--+
%e A333510                  |  |
%e A333510    *  *   *  *   *--+   *  *   *  *
%e A333510    --------------------------------
%e A333510    *  *   *--*   *  *   *  *   *--+
%e A333510           |  |                 |
%e A333510    +  +   +  *   +--*   +  *   *--*
%e A333510    |  |      |      |   |         |
%e A333510    *--*   *  +   *  +   *--+   +--*
%e A333510    --------------------------------
%e A333510    *--+   *  +   *  +   *--*   *  *
%e A333510    |         |      |   |  |
%e A333510    *  *   *--*   *  *   *  +   *--+
%e A333510    |      |         |   |      |
%e A333510    +  *   +  *   +--*   +  *   +  *
%e A333510    --------------------------------
%e A333510    *  *   *--*   *  *   *  *
%e A333510           |  |
%e A333510    *  +   *  *   *--*   *  *
%e A333510       |   |  |   |  |
%e A333510    +--*   +  +   +  +   +--+
%o A333510 (Python)
%o A333510 # Using graphillion
%o A333510 from graphillion import GraphSet
%o A333510 import graphillion.tutorial as tl
%o A333510 def A(start, goal, n, k):
%o A333510     universe = tl.grid(n - 1, k - 1)
%o A333510     GraphSet.set_universe(universe)
%o A333510     paths = GraphSet.paths(start, goal)
%o A333510     return paths.len()
%o A333510 def A333509(n, k):
%o A333510     if n == 1: return 1
%o A333510     s = 0
%o A333510     for i in range(1, n + 1):
%o A333510         for j in range(k * n - n + 1, k * n + 1):
%o A333510             s += A(i, j, k, n)
%o A333510     return s
%o A333510 def A333510(n):
%o A333510     return A333509(n, 2)
%o A333510 print([A333510(n) for n in range(1, 20)])
%Y A333510 Column k=2 of A333509.
%K A333510 nonn
%O A333510 1,2
%A A333510 _Seiichi Manyama_, Mar 25 2020