Elements of Combinatorial Analysis

[WMDhamnekar]

Homework Statement

The probability$P_m(r, n) = n^{-r} \cdot E_m(r, n)$ of finding exactly m cells empty satisfies $P_{m}(r+1, n) = P_m(r, n)\cdot \frac{n-m}{n} + P_{m+1}(r, n)\cdot \frac{m+1}{n}$

Relevant Equations

The number of distributions leaving exactly m cells empty $E_m(r, n) = \binom{n}{m} A(r, n-m) = \binom{n}{m} \displaystyle\sum_{v=0}^{n-m} (-1)^v \binom{n-m}{v}(n-m-v)^r$

$P_m(r + 1, n)= n^{-r}\cdot E_m(r + 1, n), E_m(r + 1, n)= \binom{n}{m} A(r+1, n-m) = \binom{n}{m} \displaystyle\sum_{v=0}^{n-m}(-1)^v \binom{n-m}{v}(n-m-v)^r$

$P_{m+1}(r, n) = \binom{n}{m} A(r, n-m-1) =\binom{n}{m+1} \displaystyle\sum_{v=0}^{n-m-1}(-1)^v \binom{n-m-1}{v}(n-m-1-v)^r \tag{2}$

If n=12, r=15, m=3, then $E_3(15, 12) = 5.35910901948e15, P_3(15,12)= \frac{5.35910901948e15}{12^{15}}=0.34783549783$

$P_4(15,12)=12^{-15}\cdot E_4(15,12)=12^{-15}\cdot4.32354508185e15= 0.28062173217$

$P_3(16,12)= 12^{-16}\cdot E_3(16,12)=0.354417200752$

$P_3(16,12)= 0.34783549783 \times\frac34 + 0.28062173217\times \frac13= 0.354417200762$

Is this correct way to prove?

 

[anuttarasammyak]

I am not sure which line you wrote is a question to be proved and which line are definition of the symbols.

 

[WMDhamnekar]

I am not sure which line you wrote is a question to be proved and which line are definition of the symbols.

We require to show that Homework statement is correct and true with the help of relevant equation.
I used a hypothetical example of n(cells)=12, r(objects)=15, m(empty cells) =3.

 

[anuttarasammyak]

I used a hypothetical example of n(cells)=12, r(objects)=15, m(empty cells) =3.

Was this example helpful for you to check / verify the statement ? Why do not you try simpler cases ,e.g. n=r=1, m=0?

 

[WMDhamnekar]

Was this example helpful for you to check / verify the statement ? Why do not you try simpler cases ,e.g. n=r=1, m=0?

Yes. That is very easy way to prove the homework statement with the relevant equation.

 

[pbuk]

Demonstrating that an equation works for a particular example is not a proof. You have started off well with

$$
\begin{aligned}
P_m(r + 1, n) &= n^{-r}\cdot E_m(r + 1, n) \\
E_m(r + 1, n) &= \binom{n}{m} A(r+1, n-m)
\end{aligned}
$$

However $$
\binom{n}{m} A(r+1, n-m) \ne \binom{n}{m} \displaystyle\sum_{v=0}^{n-m}(-1)^v \binom{n-m}{v}(n-m-v)^r
$$

I suggest you write expressions for $P_m(r, n)\cdot \frac{n-m}{n}$ and $P_{m+1}(r, n)\cdot \frac{m+1}{n}$ and compare terms with the correct expansion of $n^{-r}\cdot E_m(r + 1, n)$

 

[WMDhamnekar]

$[1] P_m(r,n)\cdot \frac{n-m}{n} + P_{m+1}(r,n)\cdot \frac{m+1}{n}= n^{-r} \binom{n}{m} \displaystyle\sum_{v=0}^{n-m} (-1)^v \binom{n-m}{v}(n-m-v)^r \cdot \frac{n-m}{n} + n^{-r} \binom{n}{m+1} \displaystyle\sum_{v=0}^{n-m-1}(-1)^v \binom{n-m-1}{v}(n-m-1-v)^r \cdot \frac{m+1}{n}$$[2] P_m(r + 1, n)= n^{-r}\cdot E_m(r + 1, n)=n^{-r} \binom{n}{m} A(r+1, n-m) = n^{-r}\binom{n}{m} \displaystyle\sum_{v=0}^{n-m}(-1)^v \binom{n-m}{v}(n-m-v)^r$

Now, how to show that [2] = [1]?

 

[pbuk]

Ok, that is not going to be easy; perhaps a different approach is needed (I don't think your relevant equation is actually relevant at all, and once you see it the solution is so easy you are going to kick yourself: I did!).

We are looking for the probability that after $r + 1$ balls have been distributed exactly $m$ cells are empty. Think about the balls being distributed one at a time: how can we get to this state from the possible states after $r$ balls have been distributed?

 

[WMDhamnekar]

Ok, that is not going to be easy; perhaps a different approach is needed (I don't think your relevant equation is actually relevant at all, and once you see it the solution is so easy you are going to kick yourself: I did!).

We are looking for the probability that after $r + 1$ balls have been distributed exactly $m$ cells are empty. Think about the balls being distributed one at a time: how can we get to this state from the possible states after $r$ balls have been distributed?

$P_m(r+1,n)=P_m(r, n) + P_m(1,n) = n^{-r}\cdot \binom{n}{m} \cdot \displaystyle\sum_{v=0}^{n-m} (-1)^v\cdot \binom{n-m}{v}\cdot (n-m-v)^r + n^{-r}\cdot \binom{n}{m} \cdot(n-m)$

Are these computations correct logically?

Now, are there any binomial theorem properties of any use here?

 

[pbuk]

$P_m(r+1,n)=P_m(r, n) + P_m(1,n) = n^{-r}\cdot \binom{n}{m} \cdot \displaystyle\sum_{v=0}^{n-m} (-1)^v\cdot \binom{n-m}{v}\cdot (n-m-v)^r + n^{-r}\cdot \binom{n}{m} \cdot(n-m)$

Are these computations correct logically?

No, you are not on the right track, there are no summations involved. Look at the two terms in the "answer" for the clues:

$P_m(r, n)$ is the probability that we have $m$ empty holes after r balls are placed. When we place the $(r + 1)$th ball then either it goes into one of those empty holes and there are only $m - 1$ empty, which is not what we want, or it goes into one of the $n - m$ holes that are not empty so there are still $m$ empty which is what we DO want. What is the probability of that?

What about $P_{m+1}(r, n)$?

Are there any other ways we can get to $m$ empty holes when placing the $(r + 1)$th ball?

 

[WMDhamnekar]

No, you are not on the right track, there are no summations involved. Look at the two terms in the "answer" for the clues:

$P_m(r, n)$ is the probability that we have $m$ empty holes after r balls are placed. When we place the $(r + 1)$th ball then either it goes into one of those empty holes and there are only $m - 1$ empty, which is not what we want, or it goes into one of the $n - m$ holes that are not empty so there are still $m$ empty which is what we DO want. What is the probability of that?

What about $P_{m+1}(r, n)$?

Are there any other ways we can get to $m$ empty holes when placing the $(r + 1)$th ball?

So,
$P_m(r+1,n) = n^{-r}\frac{(n-1)!}{m!(n-m-1)!}\displaystyle\sum_{v=0}^{n-m}(-1)^v\binom{n-m}{v}(n-m-v)^r + n^{-r}\frac{(n-1)!}{m!(n-m-1)!}\displaystyle\sum_{v=0}^{n-m-1}(-1)^v \binom{n-m-1}{v}(n-m-1-v)^r$

$P_m(r+1,n)=n^{-r}\binom{n-1}{m}\left[\displaystyle\sum_{v=0}^{n-m}(-1)^v\binom{n-m}{v}(n-m-v)^r +\displaystyle\sum_{v=0}^{n-m-1}(-1)^v\binom{n-m-1}{v}(n-m-1-v)^r\right]$

Now, what to do next?

 

[pbuk]

Now, what to do next?

Start again I am afraid.

We are interested in the probability of the state after placing $r + 1$ balls being exactly $m$ empty cells, $P_m(r + 1,n)$. In order to reach this state then either:

• the state after placing $r$ balls was that exactly $m$ cells were empty (with probability $P_m(r, n)$) and the $(r + 1)th$ ball was placed in an occupied cell (with probability $\frac{n-m}n$); or
• the state after placing $r$ balls was that exactly $m +1$ cells were empty (with probability $P_{m-1}(r, n)$) and the $(r + 1)th$ ball was placed in an empty cell, reducing the number of empty cells to $m$ (with probability $\frac{m+1}n$).

And that is all there is to it.