cp's OEIS Frontend

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.

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