Question:
In how many ways can $2n$ people be divided into $n$ pairs?
Approach: Well as there are $2n$ people, it is obvious that we need to chose each and everyone of them. Using simple counting, the way to divided $2n$ people into $n$ groups is $(2n)!$ However, there is the chance that some of the pairs are repeated. How exactly would I proceed to answer this question?
On
Here is another approach you could use, which gives the same answer:
1) Take an arbitrary person in the group; there are $2n-1$ choices for this person's partner.
2) Next take anyone in the remaining $2n-2$ people; there are $2n-3$ choices for this person's partner.
3) Now take anyone in the remaining $2n-4$ people; there are $2n-5$ choices for the partner of this person.
Continuing in this manner,
there are $(2n-1)(2n-3)(2n-5)\cdots3\cdot1$ ways to divide the group of $2n$ people into pairs.
There's not just a chance that some of the pairs are repeated when counting $(2n)!$, it is certain that there'll be a lot of overcounting. We can use this certainty constructively to correct for the overcounting:
Stand the $2n$ people in a line in some order. There are $(2n)!$ ways to do that.
Pair them into pairs of neighbors, but (for now) remember who is the left and right neighbor in each pair, as well as which order the pairs stand in. This means we don't lose information when doing this, and there are still $(2n)!$ possibilities.
Now forget who is the left and right member of each pair. This collapses $2^n$ previously-different combinations into one, and there are now $\frac{(2n)!}{2^n}$ possibilities.
Finally forget which pair was first, second, etc. in the line. This collapses $n!$ previously-different combinations into one, and there are now $\frac{(2n!)}{n!2^n}$ possibilities.
And now we have forgotten all we need to forget so $\frac{(2n)!}{n!2^n}$ is the final result.