# Probability of finding exactly $m$ cells empty

Another problem on combinatorics. This time I'm asking for a hint and if it is possible a general strategy when dealing with this kind of problems.

Show without using the preceding results * that the probability $p_{m}(r,n)=n^{-1}E_{m}(r,n)$ of finding exactly $m$ cells empty satisfies

$$p_{m}(r+1,n)=p_{m}(r,n)\frac{n-m}{n}+p_{m+1}(r,n)\frac{m+1}{n} \qquad \qquad (1)$$

* The results which I can't use must be

$$E_{m}(r,n)=\binom{n}{m}A(r,n-m)=\binom{n}{m}\sum_{\nu=0}^{n-m}(-1)^{\nu}\binom{n-m}{\nu}(n-m-\nu)^{r}$$ and by association $$A(r,n+1)=\sum_{k=1}^{r}\binom{r}{k}A(r-k,n)$$

By the way, $A(r,n)$ is equal to $n!S(r,n)$ where $S(r,n)$ are the Stirling numbers of the second kind.

I'm not sure how to proceed since the 'preceding result' I can't use is basically the definition for $E_{m}(r,n)$. Even if I use such definition in the left hand side of equation $(1)$, I end up with the first term $p_{m}(r,n)\frac{n-m}{m}$ and a nasty second term $\binom{n}{m}\sum_{s=0}^{n-m}(-1)^{s}\binom{n-m}{s}(1-\frac{m+s}{n})^{r}(-\frac{s}{n})$which doesn't resemble the equation $(1)$.

-
What are $r$ and $n$? – Mike Spivey Dec 20 '10 at 23:55
Sorry for that. As Ross mentioned, $r$ is the number of object to be placed in $n$ cells. – Robert Smith Dec 21 '10 at 3:00

So (looking at your last problem) $p_m(r,n)$ is the probability of finding m cells out of n empty when you scatter r objects randomly among the bins. Now you are trying to find an expression for $p_m(r+1,n)$. Think about how you can get there with $r+1$ objects. You can either have $m$ cells empty with $r$ objects and put the new one in an occupied bin, or you can have $m+1$ cells empty with $r$ objects and put the new one in an unoccupied bin. This should lead you to the equation you want.
Very nice. I have a question, though. How do you know that these two ways of getting $p_{m}(r+1,n)$ are the only ones that you need to address? For example, what about having $m+2$ cells empty with $r-1$ objects. Then you put one in one of the $m+2$ cells empty and put the other in one of the $m+1$ remaining empty cells. Why is that not a possible distribution to take into account?. – Robert Smith Dec 21 '10 at 2:58