Recurrence relation for pairing off $2n$ people

Question

I know the answer is supposed to be $$a_{2n} = (2n-1) a_{2n-2}$$ Can someone please explain why shouldn't be having $\binom{2n}{2}$ in place of $2n-1$?

Doesn't it matter which two people are paired off out of the $2n$ people and hence generating a different case each time for the remaining $(2n-2)$ people?

Answer 1

Consider the problem of pairing $2n$ people AND label one of these pairs. Then the number of ways is $$b_{2n}=\binom{2n}{2}a_{2n-2}$$ This is what we enumerate when in your formula we have $\binom{2n}{2}$ in place of $2n-1$.

Since there are $n$ possible pairs, we may "unlabel" the labelled pair by dividing by $n$: $$a_{2n}=\frac{b_{2n}}{n}=\frac{1}{n}\binom{2n}{2}a_{2n-2}=(2n-1)a_{2n-2}.$$

Answer 2

Suppose that you have people numbered from $1$ through $2n$. First you decide who gets paired with person $1$; there are $2n-1$ ways to do that. Once you’ve done that, you’re left with $2n-2$ people, who can be paired up in $a_{2n-2}$ different ways. Thus, $a_{2n}=(2n-1)a_{2n-2}$.