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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 7 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


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


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


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:


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|cite|improve this answer
Are you sure about $(2n-1)!!$? When I define $n := 2$ then there are $\frac{4!}{2^2 \cdot 2!} = \frac{24}{8} = 3$ but $(4-1)!! = 3!! = 720$ – bodokaiser Mar 17 '15 at 10:08
@bodokaiser: No, $3!!=3\cdot1=3$. $n!!$ is not the same as $(n!)!$; see here. – Brian M. Scott Mar 17 '15 at 10:10
@brian-m-scott Wow didn't know there was an extra rule for double factorials. Thank you :D – bodokaiser Mar 17 '15 at 10:13
@bodokaiser: You’re welcome; it is a rather odd notation! – Brian M. Scott Mar 17 '15 at 10:14
@bodokaiser: That would give you the number of ways of choosing one pair. But then you have to choose the other $n-1$ pairs, and you have to account for the fact that the same set of pairs can be chosen in $n!$ different orders, so in the end you get the same formula as before. – Brian M. Scott Mar 17 '15 at 10:30

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|cite|improve this answer

Your Answer


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.