Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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
    
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. –  Ross Millikan Dec 21 '10 at 3:03
    
Right! Thank you very much. –  Robert Smith Dec 21 '10 at 3:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.