Pre-interview_Test_Question_34

consider the set \{A_1,A_2,\ldots,A_{2n}\} where each A_i is a participant. there are (2n)! arrangements of this set.
we want pairings, so we want to “change” the set into the form \{(A_1,A_2),\ldots,(A_{2n-1},A_{2n})\}. there will be exactly \dfrac{2n}{2}=n pairings in any such set. now keeping the pairings of participants the same, there are n! ways of reordering this arrangement of pairings. but because in any of the arrangements the pairings are the same we will be overcounting by this factor of n!(the order doesn’t matter, the same pairs of ppl will be playing in any of the arrangements). therefore we need to divide (2n)! by n! to fix the count.
next notice how you can swap the places of the participants and still obtain the same pair of participants that will play against each other. eg. (A_1,A_2)\equiv(A_2,A_1), so we need to divide by 2 to remove half of the unwanted extra ones in the count. there are n pairs in any arrangement so dividing by 2 for each means dividing by 2^n.
\therefore we have

\begin{align} \frac{(2n)!}{n!2^n} &= \frac{\cancel{2n}(2n-1)!}{\cancel{2n}(n-1)!2^{n-1}} \\ &= \frac{(2n-1)!}{(n-1)!2^{n-1}} \end{align}
1 Like