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,

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

The solution to the recurrence is given by:

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