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

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]

Example

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

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, 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)])
(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

Crossrefs

Column k=3 of A333571.

Cf. A003685, A333511.

Sequence in context: A299337 A332611 A162484 * A259119 A039660 A333053

Adjacent sequences: A333572 A333573 A333574 * A333576 A333577 A333578

Keyword

nonn,easy

Author

Seiichi Manyama, Mar 27 2020

Extensions

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

Status

approved