# Show without using the preceding results * that the probability pm(r,n)=n^−1Em(r,n) of finding exactly 𝑚 cells empty satisfies pm(r+1,n)=pm(r,n)(n−m)/n+pm+1(r,n)(m+1)/n (1)

Show without using the preceding results * that the probability ${p}_{m}\left(r,n\right)={n}^{-1}{E}_{m}\left(r,n\right)$ of finding exactly 𝑚 cells empty satisfies
${p}_{m}\left(r+1,n\right)={p}_{m}\left(r,n\right)\frac{n-m}{n}+{p}_{m+1}\left(r,n\right)\frac{m+1}{n}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\left(1\right)$
* The results which I can't use must be
${E}_{m}\left(r,n\right)=\left(\genfrac{}{}{0}{}{n}{m}\right)A\left(r,n-m\right)=\left(\genfrac{}{}{0}{}{n}{m}\right)\sum _{\nu =0}^{n-m}\left(-1{\right)}^{\nu }\left(\genfrac{}{}{0}{}{n-m}{\nu }\right)\left(n-m-\nu {\right)}^{r}$
and by association
$A\left(r,n+1\right)=\sum _{k=1}^{r}\left(\genfrac{}{}{0}{}{r}{k}\right)A\left(r-k,n\right)$
By the way, $A\left(r,n\right)$ is equal to $n!S\left(r,n\right)$ where $S\left(r,n\right)$ are the Stirling numbers of the second kind.
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

sliceu4i
So ${p}_{m}\left(r,n\right)$ 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 $m$. 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.
###### Did you like this example?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee