# Combination of splitting elements into pairs

Here is the problem:

Suppose there is a group of 12 people. In how many different ways can the 12 people be split into six pairs?

The answer is supposed to be $\frac{12!}{2^{6} 6!}$, but what I get is $\binom{12}{2} \binom{10}{2} \binom{8}{2} \binom{6}{2} \binom{4}{2} \binom{2}{2} = \frac{12!}{2^{6}}$.

Could anybody explain why is the factorial part necessary? I think it is related to the 6! possible permutations of the pairs but why is this relevant?

Thanks!

-
(a b) (c d) is considered the same pairing as (c d) (a b) –  Alexander Thumm Apr 28 '11 at 19:28

Your answer to your question is exactly right -- it's because of the permutations of the pairs. What you calculated was the number of ways of choosing a pair from 12 times the number of ways of choosing a pair from 10 etc. -- but that overcounts the number of ways of splitting the people into pairs. For instance, you might pick Jane and John as the first pair and pick Alice and Alan as the second pair, or vice versa, and you're counting those as distinct results even though the question only asks for the number of ways of splitting into six pairs and isn't interested in the order in which you picked the pairs. You have to compensate for that overcounting by dividing by the number of orderings in which you could have picked any set of six pairs, and that's the number of permutations of six objects, which is $6!$.

-
I see. Thanks very much! –  User3419 Apr 29 '11 at 10:04

There are other ways of counting that involve less machinery. For example, imagine that you have lined the people in a row, by height, or student number, whatever.

Look at the first person in the row. Her partner can be chosen in $11$ ways. For each of these ways, think about the first person in the row who has not yet been partnered up. She has $9$ candidates for a partner. So the first two partnerings can be done in $11 \times 9$ ways.

For each of these ways, look at the first person in the row who does not yet have a mate. Her partner can be chosen in $7$ ways. Continue. We find that the number of ways to split the group of $12$ into $6$ pairs is $$11\times 9\times 7\times 5\times 3\times 1$$ (the $1$ at the end is there to make things prettier).

The above answer is of course numerically exactly the same as the $\frac{12!}{2^{6}6!}$ mentioned in your question.

You may want to solve also some closely related problems. For example, how many ways are there to divide $12$ people into $4$ groups of $3$ people each? The approach that you described, and the one that I described, each generalize nicely. If we want to divide $13$ people into $3$ groups, two with $4$ people each, and one with $5$, your kind of approach is easier to use reliably.

-
@user6312, thank you! –  User3419 Apr 30 '11 at 11:19