Basic Recursion Exercise

Question

Find a recursive formula to divide N people in to couples and singles.

The answer:

$$A_n = A_{n-1} + A_{n - 2}(n - 1)$$

Some one can explain the answer , why do we need to multiply by n-1?

Answer 1

If the people were indistinguishable, the number would simply be $\left\lfloor \dfrac{n}{2}\right\rfloor + 1$, since you can form between $0$ and $\left\lfloor \dfrac{n}{2}\right\rfloor$ pairs (both bounds inclusive).

But with distinguishable people, you can either put the new person with number $n$ into a singleton group - that gives the summand $A_{n-1}$, since there are $A_{n-1}$ ways to divide the remaining $n-1$ people - or pair the new person up with one of the $n-1$ others. Each of the $n-1$ possible pairs with person $n$ leaves $A_{n-2}$ ways to divide the remaining $n-2$ people, that gives the summand $(n-1)A_{n-2}$.