login
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

%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