Combinatorics – In How Many Ways Can We Pair Ourselves?

combinatorics

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.

Best Answer

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

Related Question