5
$\begingroup$

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?

2 Answers 2

9

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

  • 0
    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$2015-03-17
  • 1
    @bodokaiser: No, $3!!=3\cdot1=3$. $n!!$ is not the same as $(n!)!$; see [here](http://en.wikipedia.org/wiki/Double_factorial).2015-03-17
  • 0
    @brian-m-scott Wow didn't know there was an extra rule for double factorials. Thank you :D2015-03-17
  • 1
    @bodokaiser: You’re welcome; it *is* a rather odd notation!2015-03-17
  • 0
    @brian-m-scott I tried to model this problem as ${2n \choose 2}$ and interestingly this works for $2n < 8$ why does it "stop working" there?2015-03-17
  • 0
    @bodokaiser: Basically just coincidence: the two expressions happen to give the same value in those cases.2015-03-17
  • 0
    @brian-m-scott shouldn't it be possible to use ${2n \choose 2}$ and stop the over counting somehow or is this way misleading?2015-03-17
  • 1
    @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.2015-03-17
5

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