|
%I #35 Apr 23 2024 23:26:38
%S 0,1,3,30,480,12000,430920,21052080,1343381760,108519626880,
%T 10825535952000,1307042125804800,187849403155814400,
%U 31691651643235584000,6201948133744691328000,1393497414722424211200000,356287752381703180566528000,102850159977463464656842752000
%N Number of Hamiltonian cycles in the Cartesian product graph K_2 times K_n.
%C 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.
%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/RookGraph.html">Rook Graph</a>.
%H Notamathematician et al., <a href="https://mathoverflow.net/q/469606">On a A089039 and pair of sequences with simple recursion</a>, MathOverflow, 2024.
%F Sum_{k=1..floor(n/2)} binomial(n, 2k) * (2k - 1)! * ((n - k - 1)! / (k - 1)!)^2.
%F For n > 1, a(n) = A089039(n)/2. - _Mikhail Kurkov_, Feb 10 2019
%F 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
%e For n = 1, the graph is K_2 and has no Hamiltonian cycles.
%e For n = 2, the graph is C_4, with a single Hamiltonian cycle.
%e 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.
%o (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
%Y Second column of A269562.
%Y Cf. A001040, A001053, A089039 (directed cycles).
%K nonn,easy
%O 1,3
%A _Joel B. Lewis_, Aug 31 2016
| 