3

Question:

In how many ways can $2n$ people be divided into $n$ pairs?

Approach: Well as there are $2n$ people, it is obvious that we need to chose each and everyone of them. Using simple counting, the way to divided $2n$ people into $n$ groups is $(2n)!$ However, there is the chance that some of the pairs are repeated. How exactly would I proceed to answer this question?

Gummy bears
  • 3,408

2 Answers2

9

There's not just a chance that some of the pairs are repeated when counting $(2n)!$, it is certain that there'll be a lot of overcounting. We can use this certainty constructively to correct for the overcounting:

  1. Stand the $2n$ people in a line in some order. There are $(2n)!$ ways to do that.

  2. Pair them into pairs of neighbors, but (for now) remember who is the left and right neighbor in each pair, as well as which order the pairs stand in. This means we don't lose information when doing this, and there are still $(2n)!$ possibilities.

  3. Now forget who is the left and right member of each pair. This collapses $2^n$ previously-different combinations into one, and there are now $\frac{(2n)!}{2^n}$ possibilities.

  4. Finally forget which pair was first, second, etc. in the line. This collapses $n!$ previously-different combinations into one, and there are now $\frac{(2n!)}{n!2^n}$ possibilities.

And now we have forgotten all we need to forget so $\frac{(2n)!}{n!2^n}$ is the final result.

hmakholm left over Monica
  • 286,031
  • I'm sorry, but I don't seem to understand the third part. Apart from the third part, I understand everything fine. – Gummy bears Jan 03 '15 at 12:17
  • @Gummybears: After the third step, each participant knows which numbered pair he is part of, but has forgotten whether he was the first or second person to be drawn for that pair. For each result of this kind, how many initial sequences leads to that result? If we have one such initial sequence, we can construct all other ones by selecting a subset of the pairs and swapping the two members of the pairs in the subset. There are $2^n$ different subsets of the $n$ pairs. So each state after step 3 is created by $2^n$ different sequences before step 3. – hmakholm left over Monica Jan 03 '15 at 13:19
  • Okay, that makes more sense now. Thanks. – Gummy bears Jan 03 '15 at 13:51
8

Here is another approach you could use, which gives the same answer:

1) Take an arbitrary person in the group; there are $2n-1$ choices for this person's partner.

2) Next take anyone in the remaining $2n-2$ people; there are $2n-3$ choices for this person's partner.

3) Now take anyone in the remaining $2n-4$ people; there are $2n-5$ choices for the partner of this person.

Continuing in this manner,

there are $(2n-1)(2n-3)(2n-5)\cdots3\cdot1$ ways to divide the group of $2n$ people into pairs.

user84413
  • 27,211