next up previous contents
Next: Problem from a different Up: Throwing N stones into Previous: Focus on one particular   Contents

Problem solved with a recurrence

Let $ A(N,M)$ be the number of arrangements leaving none of the $ M$ bins empty [28]. We imagine adding an additional bin. This bin contains k stones ( $ 1 \leq k \leq N$) but not 0, so that we can express the number of arrangements in the other bins with $ A(N-k, M)$. Therefore, the number of arrangements leaving none of the $ M+1$ bins empty satisfies a recurrence,

$\displaystyle A(N,M+1)=\sum_{k=1}^{N} \binom{N}{k}A(N-k,M).

The solution to the recurrence is given by:

$\displaystyle A(N,M)=\sum_{\nu=0}^{M} (-1)^{\nu} \binom{M}{\nu}(M-\nu)^N.

To prove it by induction, one can plug the solution into the recurrence formula. It is necessary to change the order of summation and use the binomial formula to express $ A(N,M+1)$ as the difference of two simple sums [28].

Figure 6: Composing the recurrence formula

Tiziano Mengotti 2004-03-27