Counting with Permutations

Question

In this solution, I don't understand the final portion of the math. Why did we divide by n! and how does the equation simplify so nice and neat from that sequence.

A class has $2n$ students who must be split up into pairs. We consider two sets of pairs $S$ and $T$ different if at least one pair in the set $S$ isn't a pair in the set $T$. A pair is unordered, so we consider the pair $(1, 2)$ and $(2, 1)$ to be the same pair.

How many different sets of pairs can the class be split up into, in terms of~$n$?

For example, with $n = 2$, the answer is $3$. The sets are $\{(1, 2), (3, 4)\}$, $\{(1, 3), (2, 4)\}$ and $\{(1, 4), (2, 3)\}$.

For the first pair choose $\dbinom{2n}{2}$.

For the second pair choose $\dbinom{2n-2}{2}$.

For the third pair choose $\dbinom{2n-4}{2}$.

The total number of ways to choose is $\dbinom{2n}{2}\times \dbinom{2n-2}{2}\times \dbinom{2n-4}{2}\times \dots \times \dbinom{2}{2}$.

Therefore, the total number of different sets of pairs which the class may be split up into, in terms of $n$, is as follows: \begin{align*} \frac{ \dbinom{2n}{2} \times \dbinom{2n-2}{2} \times \dots \times\dbinom{2}{2} }{n!} &= \frac{2n!}{(2n-2)!2!} \times \frac{(2n-2)!}{(2n-4)!2!} \times\dots\times \frac{2!}{0!2!}\times \frac{1}{n!}\\ &= \frac{2n!}{2^nn!}. \end{align*}

Answer 1

You divide by $n!$ because the set of pairs is also unordered; that is, the set $\{(1, 4), (2, 3)\}$ is equivalent to the set $\{(2, 3), (1, 4)\}$. The way the product of binomial coefficients counts the pairing combinations, on the other hand, is ordered; it treats the two above sets as distinct, depending on which pair was selected first.

Since, in general, there are $n$ pairs and therefore $n!$ different but equivalent orderings of those pairs, we must divide the binomial coefficient product by $n!$ to get the desired count.

As to why the terms cancel out nicely, I'm not sure I have an interesting answer to that, except to say that they do. The factors of $2$ occur in conjunction with the numbers from $1$ to $n$ in order to get the numerators in the binomial coefficients; that's part of it.

Answer 2

The procedure by which you select a particular set of $n$ pairs counts every way to split the class into pairs exactly $n!$ times, so to get the number of splitting-into-pairs possibilities, you have to divide the number of outcomes of your step-wise process by $n!$.

For example, if $n=2$, your procedure generates the splitting $\{(1, 2), (3, 4)\}$ twice, once by choosing $(1,2)$ first, then $(3,4)$, and again by choosing $(3,4)$ as the first pair. (Do you see how the factor by which you overcount is always $n!$?)

The first $=$ in the final portion of the math is from rewriting each $a\choose b$ term as a quotient of factorials. The second and last $=$ in the simplification is obtained by cancelling out common factors between adjacent factors.