Mathematically determine ways to empty a box of toys

Question

Consider a box with $n \geq 2$ toys. We can empty it by removing two, three or four toys. How many different ways can we do this, if order matters (i.e. taking out 2, 3, then 2 toys is different from taking out 3, 2, then 2 toys)?

Obviously, this problem can be solved programmatically by iterating through all possible arrangements for two, three, or four removals, selecting only the ones that take out all the toys, and counting permutations as we do in the MISSISSIPPI problem.

Is there a more elegant mathematical solution?

Answer 1

Let $a_n$ be the number of ways to empty the box of $n$ toys. Suppose that $n\ge 5$. If we first remove $2$ toys, there are $a_{n-2}$ ways to finish emptying the box. If we first remove $3$ toys, there are $a_{n-3}$ ways to finish emptying the box. And if we first remove $4$ toys, there are $a_{n-4}$ ways to finish emptying the box. Thus,

$$a_n=a_{n-2}+a_{n-3}+a_{n-4}\tag{1}$$

for $n\ge 5$. In fact, the recurrence $(1)$ is valid for $n\ge 4$ if we set $a_0=1$. (This actually makes some sense: if $n=0$ we empty the box in one ‘move’ by removing nothing at all.) Solving for a closed form is going to be messy, since it will require factoring a quartic, but the recurrence itself makes it easy to calculate $a_n$ efficiently for reasonable values of $n$.