A333575 Number of Hamiltonian paths 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, 2, 8, 14, 38, 74, 170, 338, 724, 1448, 3000, 6008, 12240, 24512, 49504, 99104, 199232, 398720, 799616, 1599872, 3204352, 6410240, 12830208, 25664000, 51348480, 102705152, 205453312, 410925056, 821940224, 1643921408, 3288031232, 6576152576, 13152698368, 26305593344

Offset: 1

Author

Seiichi Manyama, Mar 27 2020

Keywords

• nonn
• easy

Examples

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

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• Index entries for linear recurrences with constant coefficients, signature (2,4,-8,-4,8).

Crossrefs

Column k=3 of A333571.

Cf. A003685, A333511.

Programs

PARI

Vec(x*(1 - 2*x^3 - 2*x^4 + 6*x^5 - 2*x^6 - 2*x^7) / ((1 - 2*x)*(1 - 2*x^2)^2) + O(x^40)) \\ Colin Barker, Mar 29 2020

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, is_hamilton=True)
    return paths.len()
def A333571(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 A333575(n):
    return A333571(n, 3)
print([A333575(n) for n in range(1, 15)])

Formula

G.f.: x*(1+2*x*(1+x*(4-x-11*x^2+3*x^3+7*x^4-x^5) / ((1-2*x)*(1-2*x^2)^2))). [Confirmed by Andrew Howroyd, Mar 27 2020]

a(n) = 2*a(n-1) + 4*a(n-2) - 8*a(n-3) - 4*a(n-4) + 8*a(n-5) for n>8. - Colin Barker, Mar 27 2020 [Confirmed by Andrew Howroyd, Mar 27 2020]

Extensions

Terms a(22) and beyond from Andrew Howroyd, Mar 27 2020