# In how many ways can we pair ourselves?

Say we have an even number of elements and we sort them into pairs in a way that every element belongs to a pair and no element belongs in two pairs.

Given $2n$ elements how many different arrangements of this sort can be made?

For example given elements named $1$, $2$, $3$ and $4$ we can do $\{\{1,2\},\{3,4\}\}$, $\{\{1,3\},\{2,4\}\}$ and $\{\{1,4\},\{2,3\}\}$ so we have $3$ different arrangements.

A wild guess I made is of the sort $\prod_{i=0}^{n-1} 2n-(1+2i)$.

The question arises form trying to figure out in how many ways can the earth population arrange themselves in couples where noone (or at most one poor human being) is left alone.

• Your guess is correct. – Empy2 Sep 7 '15 at 12:04
• It would be good exercise to put into words why it is the product of the odd numbers. – Empy2 Sep 7 '15 at 12:36
• These numbers are also called "double factorial" en.wikipedia.org/wiki/Double_factorial – user940 Sep 7 '15 at 14:11

We can start by looking at all the ways to arrange $2n$ numbers. This is $(2n)!$. Then within each of the $n$ pairs, there are $2$ ways to sort the numbers. So we want to divide our count by $2^n$. Lastly, we don't care about the order of the $n$ pairs themselves, so we further divide our count by $n!$. So the number of pairings of $2n$ numbers is

$$\dfrac{(2n)!}{2^nn!}.$$

Edit: This agrees with the OP's answer of $\;\prod_{i=0}^{n-1} 2n-(1+2i)$.

$$\frac1{n!}\binom{2n}2\binom{2n-2}2\cdots\binom42\binom22=\frac{(2n)!}{2^nn!}$$

Pick out $2$ out of all $2n$ to form a pair.

After that pick out $2$ out of remaining $2n-2$ to form a pair, et cetera.

Then every possibility has been counted $n!$ times (there are $n!$ orders for the pairs) so we must divide by $n!$ to repair this.

Denote the number in question by $P_{2n}$. Person number $1$ can choose his mate in $2n-1$ ways. After that there are $2n-2$ people left, which can be paired off in $P_{2n-2}$ ways. It follows that the $P_{2n}$ satisfy the recursion $$P_2=1,\qquad P_{2n}=(2n-1)\>P_{2n-2}\qquad(n>1)\ ,$$ which immediately leads to you "wild guess".

I appreciate all answers. To anyone interested in how I personally arrived to my guess: I imagined a string made by all elements, let's call it $S$, and noticed that any pairing can be uniquiely represented as another string where the $i$-th element is paired with the $i$-th element in $S$ (imagine one string on top of the other, the elements vertically aligned belong in the same pair). This strings however must satisfy that if element $a$ sats on top of $b$, then on top of $a$ we can only have $b$. In fact every string that obeys this rule uniquely determines a pairing. Counting them lead to the answer.