Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
4  
(a b) (c d) is considered the same pairing as (c d) (a b) –  Alexander Thumm Apr 28 '11 at 19:28
add comment

2 Answers

up vote 6 down vote accepted

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!$.

share|improve this answer
    
I see. Thanks very much! –  User3419 Apr 29 '11 at 10:04
add comment

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.

share|improve this answer
    
@user6312, thank you! –  User3419 Apr 30 '11 at 11:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.