|
|
A276356
|
|
Number of Hamiltonian cycles in the Cartesian product graph K_2 times K_n.
|
|
3
|
|
|
0, 1, 3, 30, 480, 12000, 430920, 21052080, 1343381760, 108519626880, 10825535952000, 1307042125804800, 187849403155814400, 31691651643235584000, 6201948133744691328000, 1393497414722424211200000, 356287752381703180566528000, 102850159977463464656842752000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
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.
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Rook Graph.
|
|
FORMULA
|
Sum_{k=1..floor(n/2)} binomial(n, 2k) * (2k - 1)! * ((n - k - 1)! / (k - 1)!)^2.
|
|
EXAMPLE
|
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.
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|