In how many distribution of n identical ball to $m$ bins, will there be exactly $k$ empty cells

88 Views Asked by At

We have $n$ identical balls which are distributed to $m$ empty cells. In how many of these distributions will there be exactly $k$ empty cells?

I thought of this solution:

We choose the $k$ empty cells - $m\choose k$. Afterwards, we distribute $1$ ball to the other $m-k$ cells (only one option - balls are the same), and then we need to choose $n-m-k$ cells with allowing repetition without importance of order from the $m-k$ cells - therefore : $n-(m-k)+(m-k)-1\choose n-m-k = n-1$ = $n-1 \choose n-m+k$

So overall: $m\choose k$ $\cdot$ $n-1 \choose n-m+k$.

Does that seem correct?

1

There are 1 best solutions below

0
On BEST ANSWER

Your final answer is correct, but there are some errors in your explanation.

There are $\binom{m}{k}$ ways to select which $k$ of the $m$ cells will be left empty. Placing one ball in each of the remaining $m - k$ cells leaves us with exactly $k$ empty cells. We must now distribute the remaining $n - (m - k) = n - m + k$ balls to the $m - k$ cells in which we have placed a ball, which is a combination with repetition problem.

If we number the $m - k$ cells in which we place a ball from $1$ to $m - k$, the number of ways to distribute the remaining $n - m + k$ balls to those $m - k$ cells is the number of solutions of the equation $$x_1 + x_2 + x_3 + \ldots + x_{m - k} = n - m + k$$ in the nonnegative integers. Since a particular solution corresponds to the placement of $m - k - 1$ addition signs in a row of $n - m + k$ ones, there are $$\binom{n - m + k + m - k - 1}{m - k - 1} = \binom{n - 1}{m - k - 1} = \binom{n - 1}{n - m + k}$$ since we must choose which $m - k - 1$ of the $n - 1$ positions required for $n - m + k$ ones and $m - k - 1$ addition signs will be filled with addition signs or, equivalently, which $n - m + k$ of the $n - 1$ positions will be filled with ones.

Consequently, there are $$\binom{m}{k}\binom{n - 1}{n - m + k}$$ ways to distribute $n$ identical balls to $m$ cells if exactly $k$ of those cells are left empty.