cp's OEIS Frontend

A333574 Number of Hamiltonian paths in the n X 2 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 A333574 #42 Sep 09 2024 15:34:51
%S A333574 1,2,4,6,10,14,20,26,34,42,52,62,74,86,100,114,130,146,164,182,202,
%T A333574 222,244,266,290,314,340,366,394,422,452,482,514,546,580,614,650,686,
%U A333574 724,762,802,842,884,926,970,1014,1060,1106,1154,1202,1252,1302,1354,1406,1460
%N A333574 Number of Hamiltonian paths in the n X 2 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.
%C A333574 Conjecture: Numbers k such that A339399(k) = A103128(k). - _Wesley Ivan Hurt_, Nov 19 2021
%H A333574 Colin Barker, <a href="/A333574/b333574.txt">Table of n, a(n) for n = 1..1000</a>
%H A333574 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-2,1).
%F A333574 G.f.: x*(1+2*x*(1-x^2+x^3)/((1+x)*(1-x)^3)).
%F A333574 From _Colin Barker_, Mar 27 2020: (Start)
%F A333574 a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4) for n>5.
%F A333574 a(n) = (9 + (-1)^(1+n) - 4*n + 2*n^2) / 4 for n>1. (End)
%F A333574 E.g.f.: ((4 - x + x^2)*cosh(x) + (5 - x + x^2)*sinh(x) - 2*(2 + x))/2. - _Stefano Spezia_, Jun 14 2023
%e A333574 a(1) = 1;
%e A333574    +--+
%e A333574 a(2) = 2;
%e A333574    +  +   *--*
%e A333574    |  |   |  |
%e A333574    *--*   +  +
%e A333574 a(3) = 4;
%e A333574    +  +   +--*   *--+   *--*
%e A333574    |  |      |   |      |  |
%e A333574    *  *   *--*   *--*   *  *
%e A333574    |  |   |         |   |  |
%e A333574    *--*   *--+   +--*   +  +
%o A333574 (PARI) N=66; x='x+O('x^N); Vec(x*(1+2*x*(1-x^2+x^3)/((1+x)*(1-x)^3)))
%o A333574 (Python)
%o A333574 # Using graphillion
%o A333574 from graphillion import GraphSet
%o A333574 import graphillion.tutorial as tl
%o A333574 def A(start, goal, n, k):
%o A333574     universe = tl.grid(n - 1, k - 1)
%o A333574     GraphSet.set_universe(universe)
%o A333574     paths = GraphSet.paths(start, goal, is_hamilton=True)
%o A333574     return paths.len()
%o A333574 def A333571(n, k):
%o A333574     if n == 1: return 1
%o A333574     s = 0
%o A333574     for i in range(1, n + 1):
%o A333574         for j in range(k * n - n + 1, k * n + 1):
%o A333574             s += A(i, j, k, n)
%o A333574     return s
%o A333574 def A333574(n):
%o A333574     return A333571(n, 2)
%o A333574 print([A333574(n) for n in range(1, 25)])
%Y A333574 Column k=2 of A333571.
%Y A333574 Cf. A333510.
%Y A333574 Cf. A103128, A339399.
%K A333574 nonn,easy
%O A333574 1,2
%A A333574 _Seiichi Manyama_, Mar 27 2020