Double Factorial: Number of possibilities to partition a set of $2n$ items into $n$ pairs

Question

I know that the partition of $2n$ items into $n$ pairs has something to do with double factorial, but I am not sure how many possibilities we exactly have.

We can choose such a partition into pairs by first choosing $n$ elements to be in one half and the remaining $n$ in the other half, which gives ${{2n} \choose n}$ possibilities. Then we can take a permutation of both sets and match them accordingly.

This gives $${{2n} \choose n} n! n!=\frac{(2n)! n! n!}{n! n!}=(2n)!$$ possibilities. But with this we overcount, since we do not want the pairs to be ordered. Each of the $n$ pairs is counted twice, wherefore we have to divide by 2 for every pair, hence $\frac{(2n)!}{2^n}$?

Well, another possiblity to do that is just to iteratively pick $2$ elements among the remaining ones, which gives ${{2n} \choose 2} {{2n-2} \choose 2} \dotsb {4 \choose 2}$

I am not sure, but I do not think that this is the same and also, I do not see the connection to double factorial. Would be very glad if you could help me with these 3 possiblities.

Thank you.

Answer 1

$\binom{2n}{n}n!n!$ overcounts in two ways -- first, as you notice, because it cares about the order within the pairs; second because it distinguishes which pair appears where in the final list of pairs.

So this way of counting gives you a way of counting ways to arrange the $2n$ elements such that there's a definite answer to "what is the second element of the 17th pair?", which means that each element has a definite place. When the dust settles, what you've done is just to count the number of ways to arrange $2n$ elements in $2n$ individually named positions -- thus $(2n)!$.

Your second way of counting repairs the first problem but not the second.

One way to get the right answer would be to correct the first one for both kind of overcounting, giving $$ \frac{(2n)!}{n! 2^n} $$ where the $n!$ in the denominator corrects for reordering the pairs themselves, and $2^n$ corrects for possibly swapping the elements of each pair.

Another way would be to say: As long as there are still unpaired elements left, take the lowest-numbered of those remaining, and select one of the rest to pair it with. This gives $$ (2n-1)(2n-3)\cdots 5\cdot 3\cdot 1 = (2n-1)!!$$ possibilites.

---

Bonus exercise: Argue symbolically that $\frac{(2n)!}{n! 2^n}=(2n-1)!!$.

Answer 2

Number the items $1$ through $2n$. There are $2n-1$ ways to choose an item to be paired with item $1$. Let $a$ be the remaining item with the smallest number; there are $2n-3$ possible choices for the item to be paired with $a$. Continuing in this fashion, we find that the entire pairing can be made in $(2n-1)!!$ different ways. To see how this compares with your attempts, note that

$$(2n-1)!!=\frac{(2n)!}{2^nn!}\;,$$

since

$$(2n)(2n-2)(2n-4)\ldots(4)(2)=2^ nn!\;.$$

In particular, your last attempt is too large by a factor of $n!$: you need to divide by $n!$ to account for the different orders in which a given pairing can be chosen.