Recursion: Dividing n people into groups of 1 or 2

Question

Let $n \ge 1 $be an integer and consider $n$ people $P_1, P_2, . . . , P_n$.

Let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group consists of either one or two people.

• Determine $A_1, A_2$, and $A_3$.

I have determined that

$A_1 = 1$

$A_2 = 2$

$A_3 = 4$

• Prove that for each integer $n \ge 3$,
$A_n = A_{n−1} + (n − 1) ·A_{n−2}$.

I cannot figure this part because I couldn't figure out how to do the proof. As I cannot figure out the sequence for $A_1,...,A_n$.

I have determined $A_4 = 10$ So it follows involution.

But I don't know how to prove. If anyone can help. It would be greatly appreciated!

Answer 1

The reccurence formula almost gives the answer.

if you have $n$ people, you have to choices for $P_n$:

1. If he is alone, then you have $A_{n-1}$ choices for partioning the remaining.
2. Otherwise he is with someone, who can be $P_1,P_2,\dots,P_{n-1}$ in each case, you then have $A_{n-2}$ choices for partioning the remaining $n-2$ people.

That is why $A_n=A_{n-1}+(n-1)A_{n-2}$.