How to find the number of perfect matchings in complete graphs?

Question

In wikipedia FKT algorithm is given for planar graphs. Not anything for complete graphs. I need to find the number of perfect matchings in complete graph of six vertices.

Answer 1

It's just the number of ways of partitioning the six vertices into three sets of two vertices each, right? So that's 15; vertex 1 can go with any of the 5 others, then choose one of the 4 remaining, it can go with any of three others, then there are no more choices to make. $5\times3=15$.

Answer 2

Another way of arriving at the formula $(2n-1)!! \left( = \frac{(2n)!}{2^n (n!)} \right)$ for $2n$ vertices is by creating cycles from matchings and matchings from cycles.

If $\mathcal{C}$ is the set of cycles, then $|\mathcal{C}| = \frac{(2n-1)!}{2}$ and every cycle gives rise to exactly $2$ matchings by deleting every other edge.

For every matching of size $n$ we can obtain $\frac{(n-1)!}{2} \cdot 2^n$ cycles. First we arrange the $n$ edges from the matching into a cycle, as if they were vertices. There are $\frac{(n-1)!}{2}$ ways of arranging them in such a manner. If we now re-expand them into edges then we have $2$ choices for every edge on how we want to orient it when connecting, giving $2^n$ options per arrangement of a matching.

With $\mathcal{M}$ the set of the matchings we have $$ 2 |\mathcal{C}| = \frac{(n-1)!}{2} \cdot 2^n |\mathcal{M}| \\ \implies |\mathcal{M}| = \frac{(2n-1)!}{(n-1)!}\cdot\frac{2}{2^n}\cdot\frac{n}{n} = \frac{(2n)!}{2^nn!} $$