A333686 Number of self-avoiding paths in (2*n+1) X 3 grid starting the upper left corner, passing through the center of grid and finishing the lower right corner.

1, 10, 101, 1105, 12046, 131399, 1433341, 15635350, 170555501, 1860475165, 20294671306, 221380909199, 2414895329881, 26342467719490, 287352249584501, 3134532277710025, 34192502805225766, 372982998579773399, 4068620481572281621, 44381842298715324430, 484131644804296287101

Offset

0,2

Links

Seiichi Manyama, Table of n, a(n) for n = 0..500

Formula

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

Conjecture: a(n) = 10*a(n-1) + 10*a(n-2) - 10*a(n-4) - 10*a(n-5) + a(n-6) for n>5.

Example

a(0) = 1;
   S--+--E
a(1) = 10;
   S--*--*   S--*--*   S--*      S--*      S--*
         |         |      |         |         |
      +--*   *--+--*      +--*      +      *--+
      |      |               |      |      |
      *--E   *--*--E         E      *--E   *--*--E
   S  *--*   S  *--*   S         S         S
   |  |  |   |  |  |   |         |         |
   *  +  *   *--+  *   *  +--*   *--+--*   *--+
   |  |  |         |   |  |  |         |      |
   *--*  E         E   *--*  E         E      *--E
a(2) = 101;
   S--*--*   S--*--*   S--*--*   S--*--*   S--*--*
         |         |         |         |         |
   *--*--*   *--*--*   *--*--*   *--*--*   *--*--*
   |         |         |         |         |
   *--+--*   *--+      *--+      *--+      *  +--*
         |      |         |         |      |  |  |
         *   *--*         *--*      *      *--*  *
         |   |               |      |            |
         E   *--*--E         E      *--E         E
   ... and so on.

Prog

(Python)
# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333685(n, k):
    if n == 0 or k == 0: return 1
    universe = tl.grid(2 * n, 2 * k)
    GraphSet.set_universe(universe)
    start, goal = 1, (2 * n + 1) * (2 * k + 1)
    paths = GraphSet.paths(start, goal).including((start + goal) // 2)
    return paths.len()
def A333686(n):
    return A333685(n, 1)
print([A333686(n) for n in range(20)])

Crossrefs

Column 1 of A333685.

Sequence in context: A289770 A290192 A290196 * A279174 A279874 A279251

Adjacent sequences: A333683 A333684 A333685 * A333687 A333688 A333689

Keyword

nonn

Author

Seiichi Manyama, Apr 02 2020

Status

approved