The number of Hamiltonian cycles in the complete bipartite graph

Question

I know that in the complete bipartite graph $K_{n,n}$ , there is $\frac{n!(n-1)!}{2}$ or $n!(n-1)!$ Hamilton cycles. wiki says first, wolfram says the second one. I know that there is $2n$ ways to specify the "start", but why it goes like $n!(n-1)!$ ?

Answer 1

As the graph is the complete bipartite graph, we can count the number of cycle as :

1. Choose an initial set
2. On the first set, you have $n$ choices for the first vertex
3. On the second again $n$ choices
4. Then $n-1$ choices
5. and so on $\ldots$

Therefore we count $H=2(n!)(n!)$ Hamiltonian cycles. However, we count each cycles $2n$ times because for any cycle there are $2n$ possibles vertices acting as "start". therefore we have $$H = \frac{2(n!)^2}{2n}=n!(n-1)!$$

Now, if you consider a cycle and its reverse as the same cycle, we you should divide this result by 2.