1
$\begingroup$

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 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 :)

$\endgroup$
  • 1
    $\begingroup$ Maybe this will help you: math.stackexchange.com/questions/1352477/…. Think of a graph on $2n$ vertices as a collection of $2n$ people, and an edge is a group of two people. $\endgroup$ – Batominovski Jul 27 '15 at 1:02
  • $\begingroup$ @Batominovski Thanks for the proof, its very nice:), but could you think of a more straight forward proof ? i.e is there an easier/shorter way to do this $\endgroup$ – KLMM Jul 27 '15 at 1:06
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.