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!

Solution 1:

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.

Solution 2:

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

Solution 3:

This is an old question, but I think it could still benefit from a simpler way to derive the solution. There are 12! ways to arrange 12 people. Each permutation corresponds to a way of splitting them in pairs. In order not to overcount, we should account for the order in each pair (divide by two 6 times) and for the fact that we can freely permute the pairs themselves (divide by 6!). No binomial coefficients necessary.

Solution 4:

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 \choose 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 \choose 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$ i,e $a$can be paired with $3$ $objects$ and $b$ with $2$ and $c$ with $1$ $object$.

which by counting gives $3!$

Therefore, from this we know that each element we choose from ${2n \choose n}$ has $n!$ ways of forming a pair.

But here is the glitch, inside ${2n \choose n}$ we have already counted for all the possible $n$ objects that can be chosen from $2n$ objects.

Therefore ${2n \choose n}n!$, 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 \choose 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$ but $NOT$ $UNIQUE$.

So, 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 $\frac{{2n \choose n}n!}{(2!)^n}$