# 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

The problem here is in choosing n objects from 2n objects and then arranging them with the remaining objects in such a way to form unique pairs. i.e., 2n C n This counts the number of ways of selecting n objects from 2n objects. The remaining n can be arranged in n! ways.

So, often are we confused that to think what does this (2n C n)n! counts. Imagine, we have 6 objects. a,b,c,d,e,f we take out a,b,c. We can pair up a with d,e,f which is 3 and b with 2 and f with 1. which is 3! Therefore, from this we know that each element we choose from (2n C n) has n! ways of forming a pair. But here is the glitch, Inside (2n C n) we have already counted for all the possible n objects that can be chosen from 2n objects. Therefore (2n C n)n!, THIS counts for both GROUP 1 {(a,d),(b,e),(c,f)} and GROUP 2 {(d,a),(e,b),(f,c)}. Here, the first elements of the subsets of 1st and the 2nd Group have been counted by (2n C n) and the second elements of each the group's subsets is just the mere arrangement of n!. Now, as we can see clearly the FIRST AND THE SECOND GROUPS are Equivalent and NOT UNIQUE. So, therefore to remove this overcounting of 2 GROUPS we divide by 2! And therefore for each of the combination we have 2! which multiplies up to (2!)^n for each of the n elements of the subsets. Which leads to Unique pairs from 2n to n pairs is given by {(2n C n)n!}/(2!)^n

-