Counting the number of different ways in which groups of one or two can be formed...

Question

I'm having trouble proving that the number of ways n>3 people can be divided into groups of either one or two is equal to:

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

I'm trying to prove this by counting but am open to suggestions.
So far, I've got:

The base cases:

$A_1 =1$

$A_2 =2$

$A_3 =4$

And I think that the first part $A_{n-1}$ is just counting all the ways if the $n$th term is added to $A_{n-1}$ on a group by itself.

I also believe that the second term $(n-1)⋅A_{n-2} $ is counting the number of groups of 1 in $A_{n-1}$ that the $n$th term can pair up with, although I don't know how to even start proving this since I can't get the logic behind exactly how it's counting these groups of 1.

I'd really appreciate any guidance on how to go about this...

Answer 1

When you have $n$ people, consider what you do with the last person.

If you let him alone, you have $A_{n-1}$ ways to group the other $n-1$ people.

If you group him with someone else, you have $n-1$ ways to do that. And after that you need to group the other $n-2$ people. That's where comes from $(n-1)A_{n-2}$

Answer 2

For such an arrangement for $n$ people, there are two cases: $n$ is by itself or $n$ is paired with someone.

For the first case, if you remove $n$, then it's just an arrangement for $n-1$ people, and so, there are $A_{n-1}$ arrangements where $n$ is by itself.

Moving on to the second case, suppose that $n$ is paired off with $i$. Then, removing $n$ and $i$, it is a valid arrangement for $n-2$ people, and so, there are $A_{n-2}$ arrangements of $n$ being paired off with $i$. Since there are $n-1$ choices for $i$, you get the recursion $$A_n = A_{n-1} + (n-1)A_{n-2}.$$

Answer 3

For future reference here is a derivation using combinatorial species. The species under consideration is $$\mathfrak{P}(\mathfrak{P}_{=1}(\mathcal{Z})+\mathfrak{P}_{=2}(\mathcal{Z})).$$ This gives the exponential generating function $$G(z) = \exp\left(\frac{z}{1!} + \frac{z^2}{2!}\right) = \exp\left(z+\frac{z^2}{2}\right).$$ Differentiating we have $$G'(z) = \exp\left(z+\frac{z^2}{2}\right) (1+z) = G(z) (1+z).$$ Extracting coefficients we obtain $$n! [z^n] G'(z) = A_{n+1} = n! [z^n] G(z) (1+z) = A_n + n! [z^n] z G(z) \\= A_n + n! [z^{n-1}] G(z) = A_n + n! \frac{A_{n-1}}{(n-1)!} = A_n + n A_{n-1}.$$

This finally yields $$A_{n+1} = A_n + n A_{n-1}$$ which is the result we were trying to prove.

Remark. What we have here is a special case or rather restriction of the species $$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ which yields the generating function of the Stirling numbers of the second kind $$G(z, u) = \exp(u(\exp(z)-1))$$ where $${n\brace k} = n! [z^n] \frac{(\exp(z)-1)^k}{k!}.$$