A276356 Number of Hamiltonian cycles in the Cartesian product graph K_2 times K_n.

0, 1, 3, 30, 480, 12000, 430920, 21052080, 1343381760, 108519626880, 10825535952000, 1307042125804800, 187849403155814400, 31691651643235584000, 6201948133744691328000, 1393497414722424211200000, 356287752381703180566528000, 102850159977463464656842752000

Offset: 1

Author

Joel B. Lewis, Aug 31 2016

Keywords

• nonn
• easy

Comments

Twice the index k in the summation formula is the number of copies of K_2 in the cycle; this accounts for the factor binomial(n,2k). The remaining factors in each summand count the ways to connect these points to the others within each copy of K_n so that the result is a single cycle.

Examples

			For n = 1, the graph is K_2 and has no Hamiltonian cycles.
For n = 2, the graph is C_4, with a single Hamiltonian cycle.
For n = 3, the graph is the complement of C_6; each Hamiltonian cycle is determined by the choice of two edges of the 3 copies of K_2 to include.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
• Eric Weisstein's World of Mathematics, Rook Graph.
• Notamathematician et al., On a A089039 and pair of sequences with simple recursion, MathOverflow, 2024.

Crossrefs

Second column of A269562.

Cf. A001040, A001053, A089039 (directed cycles).

Programs

PARI

a(n) = sum(k=1, n\2, binomial(n, 2*k) * (2*k-1)! * ((n-k-1)!/(k-1)!)^2); \\ Michel Marcus, Aug 31 2016

Formula

a(n) = Sum_{k=1..floor(n/2)} binomial(n, 2k) * (2k - 1)! * ((n - k - 1)! / (k - 1)!)^2.

For n > 1, a(n) = A089039(n)/2. - Mikhail Kurkov, Feb 10 2019

For n > 1, a(n) = ((n-1)!/2)*(A001040(n-1) + A001053(n)). - Conjectured by Mikhail Kurkov, Feb 10 2019; proved (see MO link) by Max Alekseyev, Apr 23 2024