Prove the number of Hamiltonian cycles of $K_n,_n$ for $n\ge2$ is $\frac{n!(n-1)!}{2}$

Question

In wiki , I find the number of Hamiltonian cycles of $K_n,_n$ for $n\ge2$ is $\frac{n!(n-1)!}{2}$

Is it true and how to prove it ?

Answer 1

Indeed it's true. Let the bipartitions be $A$ and $B$, and without loss of generality let us start our cycle at a vertex $a_1\in A$. Our next vertex must be in $B$, and since we are working with the complete bipartite graph, we are free to choose any of the $n$ vertices of $B$, say $b_1$. Now for our third vertex, we return to $A$, and we can choose any vertex of $A$ except $a_1$ which we've already used, which gives $n-1$ choices.

You can see that by continuing this pattern, we will have a sequence of vertices $$a_1,\ b_1,\ a_2,\ b_2, a_3,\ b_3,\ \cdots,$$ eventually returning to $a_1$ to form a Hamiltonian cycle. At each vertex $a_k$, for $k>1$, we have $n-k+1$ choices because we must exclude the previous $k-1$ vertices of $A$ which we've used already. Likewise, at each $b_k$, for $k\ge 1$ (note that we fixed $a_1$ but not $b_1$, so we count $k=1$ here, whereas we do not for the $A$ vertices), we have $n-k+1$ choices as well.

Multiplying all these choices together, we get a total of $n!(n-1)!$ oriented cycles. The factor of $(n-1)!$ comes from our choices of $A$ vertices, and the factor of $n!$ comes from our choices of $B$ vertices. But the cycle we get by choosing $$a_1,\ b_1,\ a_2,\ b_2,\ a_3,\ b_3,\ \cdots,$$ is the exact same as the cycle we get by choosing $$a_1,\ b_n,\ a_n,\ b_{n-1},\ a_{n-1},\ b_{n-2},\ a_{n-2}, \cdots,$$ just that we are choosing the vertices in the opposite order. Therefore we must divide by $2$ to take care of the double counting of cycles due to orientation. This gives the final count at $n!(n-1)!/2$, precisely what you get.