Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Apparently, there are $\frac{(2n)!}{2^nn!}$ ways to break $2n$ people into partnerships. Why?

An explanation reads that there are $2n!$ ways to line people up. If we just pair adjacent people in the line up, we would have overcounted. So we must divide by $2^n n!$.

My question is why do we divide by $2^n n!$ specifically to adjust for overcounting?

Furthermore, this problem can apparently be solved by taking a skip factorial of odd values:

$(2n-1)(2n-3)(2n-5) ... (5)(3)(1)$

Why is that so? What does this skip factorial have to do with the problem?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

To see where the double factorial comes from, imagine numbering the people from $1$ through $2n$. There are $2n-1$ possible choices for $1$’s partner; those two are now out of the pool. The smallest unpaired number is now either $3$ or $2$, depending on whether $1$’s partner is $2$ or not; whichever it is, call it $m$. Now choose a partner for $m$; it can’t be $1$ or $1$’s partner, and it can’t be $m$, so there are $2n-3$ choices. Continue in this fashion. After you’ve formed $k$ pairs, let $m$ be the smallest unpaired number, and find a partner for $m$; it can’t be one of the $2k$ people already paired up, and it can’t be $m$, so you have $2n-2k-1=2n-(2k+1)$ choices. By the time you get down to the last two people, you’ll have only one choice. The total number of ways of making the choices is therefore

$$(2n-1)\cdot(2n-3)\cdot\dots\cdot3\cdot1=(2n-1)!!\;.$$

Now let’s look at the other explanation. We want to see how many of the $(2n)!$ ways of lining up the people and pairing adjacent ones lead to the same set of $n$ pairs. Let’s say that we number them $1$ through $2n$ from left to right, so that for $k=1,\dots,n$ person $2k-1$ is paired with person $2k$:

$$(p_1p_2)(p_3p_4)\dots(p_{2n-1}p_{2n})\;.\tag{1}$$

We can shuffle the $n$ pairs as pairs in any way we like, and it won’t change the partnerships: the lineup

$$(p_3p_4)(p_1p_2)\dots(p_{2n-1}p_{2n})(p_7p_8)\tag{2}$$

produces the same partnerships as the lineup in $(1)$. There are $n!$ ways of shuffling the pairs while keeping them completely intact, as in $(2)$. But it also doesn’t change the partnerships if we reverse some pairs:

$$(p_4p_3)(p_1p_2)\dots(p_{2n}p_{2n-1})(p_7p_8)$$

has the same partnerships as the lineup in $(2)$, even though I reversed the placement of $p_3$ and $p_4$ within their pair, as well as that of $p_{2n-1}$ and $p_{2n}$ within theirs. Thus, we have $n!$ ways to shuffle the pairs as pairs, and for each pair a two-way choice of whether or not to reverse the order of its members, for a grand total of $2^nn!$ different lineups that result in the same partnership. Thus, $(2n)!$ really does overcount by a factor of $2^nn!$, and the correct answer must be $\frac{(2n)!}{2^nn!}$.

Finally, we can verify that the two answers are the same:

$$\begin{align*} \frac{(2n)!}{2^nn^!}&=\frac{\Big((2n)\cdot(2n-2)\cdot(2n-4)\cdot\ldots\cdot2\Big)\Big((2n-1)\cdot(2n-3)\cdot\ldots\cdot3\cdot1\Big)}{2^nn!}\\ &=\frac{2n\cdot2(n-1)\cdot2(n-2)\cdot\ldots\cdot2(1)}{2^nn!}\cdot(2n-1)!!\\ &=\frac{2^nn!}{2^nn!}\cdot(2n-1)!!\\\\ &=(2n-1)!!\;. \end{align*}$$

share|improve this answer

Think about it like this: the $n$ pairs of people can be ordered in $n!$ different ways. Then, each pair can be flipped or not, which explains the additional $2^n$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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