2
$\begingroup$

Given $12$ balls and $10$ cells, each of them is numbered by 1-10, what is the probability that exactly 9 cells will contain at least one ball?

My Attempt:

First, $|\Omega| = \binom{21}{10}$.

Now, I tried using a generating function in order to solve the question.

then $x_1 +x_2 +x_3 +x_4 +x_5 +x_6 +x_7 +x_8 +x_9 +x_{10} = 12$.

Now, how do I find all natural solutions for this equation as there must be

$x_j \in {x_1,x_2 ,x_3 ,x_4 ,x_5 ,x_6 ,x_7 ,x_8 ,x_9 ,x_{10}} :x_j =0$, and for every $x_i \neq x_j: 1 \le x_i \le 4$.

I tried to solve it using the equation $x_1 +x_2 +x_3 +x_4 +x_5 +x_6 +x_7 +x_8 +x_9 = 12$, but that wouldn't provide me the right answer as the distributions of which cell is empty are not counted for that equation.

$\endgroup$
1
  • 1
    $\begingroup$ Stars and bars! $\endgroup$ Nov 22, 2019 at 17:13

1 Answer 1

2
$\begingroup$

There are $10^{12}$ ways to assign the balls to the cells, each of which we assume is equally likely. (It's easy to get off on the wrong foot in this problem by overlooking this assumption, for example by assuming that all non-negative integer solutions to $x_1+x_2+ \dots +x_{10} = 12$ are equally likely, which is a very unlikely assumption.) We want to count all the assignments in which exactly one cell is empty.

To do this, we will apply a variation of the Principle of Inclusion/Exclusion (PIE). Let's say an assignment of balls to cells has "property $i$" if cell $i$ is empty, for $i = 1,2,3,\dots ,10$, so our goal is to find the number of arrangements with exactly one of the properties. Further, we define $S_j$ as the total number of assignments which have $j$ of the properties (with over-counting), for $j = 1, 2, 3, \dots ,9$. Then we have $$S_j = \binom{10}{j} (10-j)^{12}$$ for $1 \le j \le 9$, since there are $\binom{10}{j}$ ways to pick the empty cells and $(10-j)^{12}$ ways to assign the balls to the remaining cells.

The variation of PIE we want to apply is that if there are $n$ properties, then the number of arrangements with exactly $m$ of the properties is $$N_m = S_m - \binom{m+1}{m} S_{m+1} + \binom{m+2}{m} S_{m+2} - \dots + (-1)^{n-m} \binom{n}{m}S_n$$ (Reference: Applied Combinatorics, Second Edition by Allan Tuckser, Section 8.2, Theorem 2; or An Introduction to Probability Theory and Its Applications, Volume I, Third Edition, by William Feller, Section IV.3.) The case we are interested in is $m=1$, $n=9$, so $$N_1 = S_1 - \binom{2}{1} S_2 + \binom{3}{1} S_3 - \dots + \binom{9}{1}S_9$$ which yields $N_1 \approx 8.08315 \times 10^{10}$. Therefore the probability of having exactly one cell empty is $$\frac{N_1}{10^{12}} \approx \boxed{0.0808315}$$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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