%I #25 Feb 17 2021 10:51:51
%S 126,1344,2930,28060,55230,538744,969378,10066228,16284862,186362560,
%T 265582226,3447630284,4238980734,64031790664,66561185858,
%U 1197008258212,1031815027710,22548844488592,15830131853490,428115681210300,240803790623806,8188893146929816
%N Number of Hamiltonian cycles in C_4 X C_n.
%C The sequence is not monotone, although it seems to be.
%C It has two monotone subsequences depending on the parity of n.
%H Seiichi Manyama, <a href="/A216588/b216588.txt">Table of n, a(n) for n = 3..100</a>
%H Artem M. Karavaev, <a href="https://web.archive.org/web/20161024010518/http://flowproblem.ru/cycles/hamilton-cycles">Hamilton Cycles: Flow Problem</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TorusGridGraph.html">Torus Grid Graph</a>
%F a(n) = P(n) + Q(floor(n/2)) if n is even and a(n) = P(n) + R(floor(n/2)) if n is odd, where P(n) = (2*n + 1)*cosh(2*n*arctanh(sqrt(1/3))) - (n/sqrt(3))*sinh(2*n*arctanh(sqrt(1/3))) + cos(Pi*n/2) - sin(Pi*n/2), Q(n) = (4^n - 16*3^n - 4)/3 + 8*2^(n/2)*cos(n*arctan(sqrt(7))) + 4*2^n*cosh(2*n*arctanh(sqrt(2/3))) - 2*cosh(2*n*arctanh(sqrt(1/2))), R(n) = -2*(n + 1)*(2 - (-1)^n).
%F G.f.: -48*x^2 - 2*x - 17/3 + (1 - x)/(x^2 + 1) + 1/(6*(2*x + 1)) + (x + 1)/(x^2 - 2*x - 1) - 1/((x - 1)^2) + (8 - 4*x^2)/(2*x^4 - x^2 + 1) + (-16 + 62*x)/(x^2 - 4*x + 1)^2 - 2/3/(x + 1) + 1/((x + 1)^2) + (17 + 3*x)/(x^2 - 4*x + 1) + (-2 - 4*x)/(2*x^2 - 4*x - 1) + 2/3/(x - 1) - 1/(6*(2*x - 1)) + (1 - x)/(x^2 + 2*x - 1) + (-2 + 4*x)/(2*x^2 + 4*x - 1) + 16/3/(3*x^2 - 1) + 2*x/(x^2 + 1)^2.
%F Asympt.: a(n) ~ 2*(2 + sqrt(6))^n if n is even and
%F a(n) ~ ((1 - 1/(2*sqrt(3)))*n + 1/2)*(2 + sqrt(3))^n if n is odd.
%p P := n -> (2*n+1)*cosh(2*n*arctanh(sqrt(1/3))) - (n/sqrt(3))*sinh(2*n*arctanh(sqrt(1/3))) + cos(Pi*n/2) - sin(Pi*n/2):
%p Q := n -> (4^n-16*3^n-4)/3+8*2^(n/2)*cos(n*arctan(sqrt(7))) + 4*2^n*cosh(2*n*arctanh(sqrt(2/3)))-2*cosh(2*n*arctanh(sqrt(1/2))):
%p R := n -> -2*(n+1)*(2-(-1)^n):
%p a := n -> expand(P(n)) + (1 - n mod 2)*expand(Q(floor(n/2))) + (n mod 2)*R(floor(n/2)):
%p seq(a(n),n=3..24);
%Y Row 4 of A270273. Cf. A194952.
%K nonn
%O 3,1
%A _Artem M. Karavaev_, Sep 09 2012