%I #40 Mar 30 2020 08:53:50
%S 1,2,8,14,38,74,170,338,724,1448,3000,6008,12240,24512,49504,99104,
%T 199232,398720,799616,1599872,3204352,6410240,12830208,25664000,
%U 51348480,102705152,205453312,410925056,821940224,1643921408,3288031232,6576152576,13152698368,26305593344
%N 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.
%H Andrew Howroyd, <a href="/A333575/b333575.txt">Table of n, a(n) for n = 1..200</a>
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,4,-8,-4,8).
%F 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]
%F 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]
%e a(1) = 1;
%e +--*--+
%e a(2) = 2;
%e + *--* *--* +
%e | | | | | |
%e *--* + + *--*
%o (Python)
%o # Using graphillion
%o from graphillion import GraphSet
%o import graphillion.tutorial as tl
%o def A(start, goal, n, k):
%o universe = tl.grid(n - 1, k - 1)
%o GraphSet.set_universe(universe)
%o paths = GraphSet.paths(start, goal, is_hamilton=True)
%o return paths.len()
%o def A333571(n, k):
%o if n == 1: return 1
%o s = 0
%o for i in range(1, n + 1):
%o for j in range(k * n - n + 1, k * n + 1):
%o s += A(i, j, k, n)
%o return s
%o def A333575(n):
%o return A333571(n, 3)
%o print([A333575(n) for n in range(1, 15)])
%o (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
%Y Column k=3 of A333571.
%Y Cf. A003685, A333511.
%K nonn,easy
%O 1,2
%A _Seiichi Manyama_, Mar 27 2020
%E Terms a(22) and beyond from _Andrew Howroyd_, Mar 27 2020