login
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.
2
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
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.
Sequence in context: A299337 A332611 A162484 * A259119 A039660 A333053
KEYWORD
nonn,easy
AUTHOR
Seiichi Manyama, Mar 27 2020
EXTENSIONS
Terms a(22) and beyond from Andrew Howroyd, Mar 27 2020
STATUS
approved