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

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?

-

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*}

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

-