My textbook presents the following story proof for partnership counting:
Let's use a story proof to show that
$$\dfrac{(2n)!}{2^n \cdot n !} = (2n – 1)(2n – 3) \dots 3 \cdot 1$$
Story proof: We will show that both sides count the number of ways to break $2n$ people into $n$ partnerships. Take $2n$ people, and give them ID numbers from $1$ to $2n$. We can form partnerships by lining up the people in some order and then saying the first two are a pair, the next two are a pair, etc. This overcounts by a factor of $n! \cdot 2^n$ since the order of pairs doesn't matter, nor does the order within each pair. Alternatively, count the number of possibilities by noting that there are $2n – 1$ choices for the partner of person 1, then $2n – 3$ choices for person 2 (or person 3, if person 2 was already paired to person 1), and so on.
I'm struggling to understand how this is overcounting by a factor of $2^n \cdot n !$.
I would appreciate it if people could please take the time to break down as to how this was figured out.
Best Answer
We assume at the start that the pairs formed are ordered, both within the pair (A, B not the same as B, A) and between the pairs (this can be interpreted as the pairs standing side-by-side, in a row). Now there are certain transformations that we can make to this actual arrangement of people so that the same pairs still result, and the number of such transformations will be the overcounting factor.
We can treat pairs as units, and permute all of them; the same pairs will still be there. Since all pairs are distinct, there are $n!$ ways to do this.
Independently of this (justifying the multiplication), we can choose whether or not to swap the people in each pair, which is one of $2$ possibilities for each of $n$ pairs, for $2^n$ ways in all.
Thus, multiplying, we see that each combination of pairs has been counted $n!2^n$ times, so we divide by that number to get the true amount.