2
$\begingroup$

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

  • 0
    Sorry for that. As Ross mentioned, $r$ is the number of object to be placed in $n$ cells.2010-12-21

1 Answers 1

4

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.

  • 0
    Right! Thank you very much.2010-12-21