How many different perfect matchings does a complete bipartite graph $K_{n,n}$ have?
Here is my reasoning:
Initially, I have $2n$ choices for vertices. Then I can combine one of these vertices with $n$ choices for a matching vertex (since it must be with a vertex in the other partition).
Next I only have $2n-2$ choices for vertices, and $n-1$ choices for matching vertices. Thus, total number of possibilities $2n*n*(2n-2)*(n-1)…$. However, I have to eliminate any redundancy. Hence,
$$\frac{2n*n*(2n-2)*(n-1)…}{n! (2!)^n}=\frac{(2n)!!(n!)}{n!(2!)^n}=\frac{(2n)!!}{(2!)^n}.$$
$n!$ because we have $n$ matchings and $(2!)^n$ to remove the redundancy between each of the $n$ matchings.
Could anyone verify this is correct?
Thanks!
Best Answer
If you cancel all those factors $2$ you get a simpler form of answer, which you can recover in a different way by numbering the vertices of one set of $n$, and simply choosing matched vertices from the other set in order.
So the proof is fine, but it isn't the simplest way to get the result.