A216588 Number of Hamiltonian cycles in C_4 X C_n.

126, 1344, 2930, 28060, 55230, 538744, 969378, 10066228, 16284862, 186362560, 265582226, 3447630284, 4238980734, 64031790664, 66561185858, 1197008258212, 1031815027710, 22548844488592, 15830131853490, 428115681210300, 240803790623806, 8188893146929816

Offset: 3

Author

Artem M. Karavaev, Sep 09 2012

Keywords

• nonn

Comments

The sequence is not monotone, although it seems to be.

It has two monotone subsequences depending on the parity of n.

Links

• Seiichi Manyama, Table of n, a(n) for n = 3..100
• Artem M. Karavaev, Hamilton Cycles: Flow Problem.
• Eric Weisstein's World of Mathematics, Hamiltonian Cycle
• Eric Weisstein's World of Mathematics, Torus Grid Graph

Crossrefs

Row 4 of A270273. Cf. A194952.

Programs

Maple

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):
a := n -> expand(P(n)) + (1 - n mod 2)*expand(Q(floor(n/2))) + (n mod 2)*R(floor(n/2)):
seq(a(n),n=3..24);

Formula

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).

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.

Asympt.: a(n) ~ 2*(2 + sqrt(6))^n if n is even and

a(n) ~ ((1 - 1/(2*sqrt(3)))*n + 1/2)*(2 + sqrt(3))^n if n is odd.