1
$\begingroup$

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?

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

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.