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?
Best Answer
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$.