# Understanding overcounting

I'm trying to understand how to adjust for overcounting. I find the following example to be very hard to understand, i.e., I understand all the words and their meanings, but I struggle to feel "convinced".

Show that:

$$\frac{(2 n) !}{2^{n} \cdot n !}=(2 n-1)(2 n-3) \cdots 3 \cdot 1$$

Intuitive explanation (via a story) given by the textbook:

$$\begin{array}{l}\text { We will show that both sides count the number of ways to break } 2 n \\ \text { people into } n \text { partnerships. Take } 2 n \text { people, and give them ID numbers from } 1 \text { to } \\ 2 n \text { . We can form partnerships by lining up the people in some order and then saying } \\ \text { the first two are a pair, the next two are a pair, etc. This overcounts by a factor } \\ \text { of } n ! \cdot 2^{n} \text { since the order of pairs doesn't matter, nor does the order within each } \\ \text { pair. Alternatively, count the number of possibilities by noting that there are } 2 n-1 \\ \text { choices for the partner of person } 1, \text { then } 2 n-3 \text { choices for person } 2 \text { (or person } 3, \text { if } \\ \text { person } 2 \text { was already paired to person } 1 \text { ), and so on. }\end{array}$$

Can someone explain to me 1) why the factor is $$n! \cdot 2^n$$ and 2) how is the RHS derived?

• See if this answer helps. – Brian M. Scott Sep 16 at 3:10
• At least it's easier than overstanding undercounting ;) – Greg Martin Sep 16 at 7:05

The first part says if we have say ABCDEF, then (AB)(CD)(EF) = (BA)(CD)(EF), and also (AB)(CD)(EF) = (CD)(AB)(EF), with there being $$2^n$$ variations of the first type, and $$n!$$ variations of the second.
Then we also have $$A$$ can be partnered with $$BCDEF$$, then mystery person $$x$$ can be partnered with the remaining $$3$$, etc. .
And $$\frac{6\cdot5\cdot4\cdot3\cdot2\cdot1}{8\cdot3\cdot2\cdot1} = \frac{6\cdot5\cdot4\cdot3\cdot2\cdot1}{6\cdot4\cdot2} = 5\cdot3\cdot1$$.