2

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?

Robert Z
  • 145,942
ps_
  • 73
  • I don't know where I'm wrong, but I keep getting $a_{2n+2} = a_{2n} + 2n(2n-1) a_{2n-2}$ – Alex Dec 01 '16 at 19:28

2 Answers2

3

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

Brian M. Scott
  • 616,228
  • Yeah, But what if we paired off the second person with someone ? The remaining 2n-2 people will possibly constitute a different set right ? So shouldn't that be accounted for ? If the question was about climbing stairs or something alike and 'sequential' in nature, I would have been able to make sense out of such arguments since there won't be any possibility of climbing step #2 before having already climbed step #1 in the process. – ps_ Dec 05 '16 at 06:57
  • 1
    @PSuniq: No: even if you start by pairing up the second person, at some point you're going to form a pair that includes the first person. Thus, you're going to end up with one of the arrangements that I counted in my answer: you don't get anything new. – Brian M. Scott Dec 05 '16 at 07:09
  • Alright, Person 1 would only have 2n-1 options for a partner and eventually be paired only in those many number of ways and hence the factor of 2n-1 makes sense. :) – ps_ Dec 05 '16 at 07:09
2

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

Robert Z
  • 145,942