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
    What are $r$ and $n$?2010-12-20
  • 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
    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?.2010-12-21
  • 0
    The case of m+2 cells empty with r-1 objects, then filling two empty cells is covered by having m+1 empty with r objects. If you are going to have m empty with r+1, you must have had either m or m+1 empty at the time you had r. When you figured out the probability of m+1 empty with r objects you considered m+2 empty with r-1 and also m+1 empty with r-1, and so on.2010-12-21
  • 0
    Right! Thank you very much.2010-12-21