Find the total number of matchings in a complete graph with even number of vertices I am trying to solve questions from a Walk through combinatorics.., I came across this proof which I was unable prove:
Determine the number of perfect matchings for a complete graph with 2n vertices.
I don't know how to approach this, I have tried counting..
The answer is:  $$ \frac{(2n)!}{n!2^n}. $$
Please help me with this, thanks :)
 A: There is an old principle in combinatorics.  To count the number of sheep in your field, count the number of legs and then divide by four, the number of legs per sheep.
Look at the expression $$\frac{(2n)!}{2^n n!}.$$
Here $(2n)!$ is the number of permutations of your set of $2n$ things.  Given such a permutation, can you think of a simple way of getting a matching?  Once you have this, you can show that each matching shows up in the same number of permutations, which ought to be $2^n n!$ from the above formula.
A: I wasn't able to figure out the answer without looking at the expression provided in the post. The expression itself is quite telling though. As already mentioned in another answer, we just have to see how $2^n*n!$ arrangements out of all the $(2n)!$ ones, correspond to the same matching.
Let's look at one of the $(2n)!$ arrangements shown below and see how it corresponds to a matching in a complete graph-
A matching in a graph
Every arrangement of $2n$ vertices can be divided into two halves of $n$ vertices each and numbered as shown in the figure above. We can define a matching $M$ as set of pairs of vertices $(l_i, r_i)$ for $1<=i<=n$. We can change this arrangement in following two ways so that it will still correspond to the same matching-


*

*Permute any of the two sets of vertices and arrange the other set in lock-step to ensure that $l_i$ is always matched with $r_i$. This can be done in $n!$ ways.

*Interchange $l_i$ and $r_i$ for any number of pairs. Every pair has $2$ configurations - $(l_i, r_i)$ and $(r_i, l_i)$. You can choose any configuration independently for each pair. Hence this can be done in $2^n$ ways.


Both the above adjustments can be done independently and hence there are $2^n*n!$ ways to arrange a set of vertices and still keep the same matching. Hence total number of unique matchings is $(2n)!/(2^n*n!)$.   
A: Let $f(n)=\frac{(2n)!}{n!2^n}$. The idea is to proceed by induction on $n$, the base case being trivial. So suppose that $f(n-1)$ is the number of perfect matchings on a complete graph with $2(n-1)$ vertices. 
Consider a complete graph on $2n$ vertices and fix a vertex $v$. Any matching $M$ of this $K_{2n}$ contains an edge $e$ incident to $v$, say $e=(v,w)$. Now $M\setminus \{e\}$ is a matching of $K_{2n}\setminus\{v,w\}\simeq K_{2n-2}$. Since there are $2n-1$ choices for $e$, it follows that the number of complete matchings of $K_{2n}$ is $(2n-1)f(n-1)$. I'll leave it to you to verify that $(2n-1)f(n-1)=f(n)$. 
