# Mathematically determine ways to empty a box of toys

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?

• OEIS A013979 Commented Mar 14, 2021 at 1:56
• Something like $0.36347969198357 \times 1.46557123187677^n + \frac{(-1)^n}{3}$ seems not far away Commented Mar 14, 2021 at 2:10
• This is exactly what I was interested in... Thanks! Commented Mar 14, 2021 at 5:02

## 1 Answer

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

• If $n=0$ then you can empty it in $0$ moves, but there is only $1$ way of doing so and here we are counting the ways so $a_0=1$. If you also say $a_n=0$ for $n<0$, as there is no way of getting to empty then your recurrence (1) is valid for $n>0$ Commented Mar 14, 2021 at 1:51