# what's the probability of putting r balls into n cells with no cells empty?

I'm reading the book An Introduction to Probability Theory and Its Applications by William Feller and trying to solve the problems after chapters. I can figure out the probability can be rewritten as

$$A(r, n+1) = \sum_{k=1}^{r} {r \choose k}A(r-k, n)$$

which explained clearly by this question (Distribution of $r$ balls into $n$ cells leaving none of the cells empty.)

But, I cannot make it out that $$A(r, n+1)$$ has the final result as

$$A(r, n) = \sum_{v=0}^{n} (-1)^v{n \choose v}(n-v)^r$$

How does it get there? Any hints will be really appreciated!

• Maybe you can try induction? – corindo Sep 17 '15 at 2:33

In this case $A(r,n)$ seems to be the number of ways to put $r$ balls in $n$ boxes so none is empty.
Clearly The first summad gives us all of the possible asignments ($\binom{n}{0}n^r=n^r$).
The next term is $-1\binom{n}{1}(n-1)^r$. This is equal to all of the permutations in which the first box is empty, plus the number of assignments in which the second box is empty and so on.