I am trying to solve this question:
Let us assume we are distributing 12 different balls between 8 numbered cells, so that each distribution of balls into cells is obtained with equal probability. What is the probability that there is no empty cell?
At first I gave to each ball an unique ID, such that:
1 = ball number 1,
2 = ball number 2, and so on.
Now i defined $\Omega =\left\{ \left( x_{1},\ldots ,x_{12}\right) | \forall i,x_{i}\in \left[ 8\right] \right\} =\left[ 8\right] ^{12}$, and so the event we want to compute is:
$A=\{ \left( x_{1},\ldots ,x_{12}\right) \in \Omega | \forall i\in \left[ 8\right] \exists j\in \left[ 12\right] ,x_{j}=i \}$.
At first I tried to work with $A^{c}$, but then I noticed that I have duplicates, so I tried to compute $|A|$ directly.
I said, in order for no cell to be empty, we will choose 8 balls out of the 12 and distribute them into the eight cells, so that each cell contains exactly one ball. Then, we will distribute the remaining four balls into the eight cells and finish.
So let's do the math:
- Choose 8 unique balls out of 12 is $\begin{pmatrix} 12 \\ 8 \end{pmatrix}$
- Distribute the balls to the cells is $8!$
- Then, distribute the remaining four is $8^{4}$
So, overall we have: $|A| = \begin{pmatrix} 12 \\ 8 \end{pmatrix} \cdot 8! \cdot 8^{4}$
Now, $|\Omega| = 8^{12}$, so finally we get:
$\mathbb{P}(A) = \dfrac{\begin{pmatrix} 12 \\ 8 \end{pmatrix}\cdot 8!\cdot 8^{4}}{8^{12}} = 1.18961 >1$.
I don't understand what I'm doing wrong, so would glad for help.
Best Answer
Method 1: We use the Inclusion-Exclusion Principle to count the favorable cases.
There are eight choices for each of the $12$ balls, so there are $8^{12}$ possible distributions. From these, we must subtract those distributions which miss one or more of the cells. There are $\binom{8}{k}$ ways to exclude $k$ of the eight cells from receiving a ball and $(8 - k)^{12}$ ways to distribute the balls to the remaining $8 - k$ cells. By the Inclusion-Exclusion Principle, the number of ways to distribute $12$ distinct balls to eight cells so that no cell is left empty is $$8^{12} - \binom{8}{1}7^{12} + \binom{8}{2}6^{12} - \binom{8}{3}5^{12} + \binom{8}{4}4^{12} - \binom{8}{5}3^{12} + \binom{8}{6}2^{12} - \binom{8}{7}1^{12} + \binom{8}{8}0^{12}$$
To see what you are doing wrong, we need to do a direct count.
Method 2: We perform a direct count of the favorable cases.
The number $12$ can be partitioned into eight parts in five ways: \begin{align*} 12 & = 5 + 1 + 1 + 1 + 1 + 1 + 1 + 1\\ & = 4 + 2 + 1 + 1 + 1 + 1 + 1 + 1\\ & = 3 + 3 + 1 + 1 + 1 + 1 + 1 + 1\\ & = 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1\\ & = 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 \end{align*}
Five balls in one cell and one ball in each of the other seven cells: There are eight ways to select the cell which receives five balls, $\binom{12}{5}$ ways to select the balls that are placed in that cell, and $7!$ ways to distribute the remaining seven balls to the remaining seven cells so that each of those cells receives one ball. Hence, there are $$\binom{8}{1}\binom{12}{5}7!$$ such distributions.
Four balls in one cell, two balls in another cell, and one ball in each of the other six cells: There are eight ways to select the cell which receives four balls, $\binom{12}{4}$ ways to select the four balls that are placed in that cell, seven ways to select the cell which receives two balls, $\binom{8}{2}$ ways to select the balls that are placed in that cell, and $6!$ ways to distribute the remaining six balls to the remaining six cells so that each of those cells receives one ball. Hence, there are $$\binom{8}{1}\binom{12}{4}\binom{7}{1}\binom{8}{2}6!$$ such distributions.
Three balls each in two cells and one ball each in the other six cells: There are $\binom{8}{2}$ ways to select the two cells that will each receive three balls, $\binom{12}{3}$ ways to select the three balls that will be placed in the leftmost of those two cells, $\binom{9}{3}$ ways to select the three balls that will be placed in the other selected cell, and $6!$ ways to distribute the remaining six balls to the remaining six cells so that each of those cells receives one ball. Hence, there are $$\binom{8}{2}\binom{12}{3}\binom{9}{3}6!$$ such distributions.
Three balls in one cell, two balls each in two other cells, and one ball each in the other five cells: There are eight ways to select the cell that receives three balls, $\binom{12}{3}$ ways to select the three balls that will be placed in that cell, $\binom{7}{2}$ ways to select the two cells that will receive two balls each, $\binom{9}{2}$ ways to select the two balls that will be placed in the leftmost of those cells, $\binom{7}{2}$ ways to select the two balls that will be placed in the other selected cell, and $5!$ ways to distribute the remaining five balls to the remaining five cells so that each cell receives one of those balls. There are $$\binom{8}{1}\binom{12}{3}\binom{7}{2}\binom{9}{2}\binom{7}{2}5!$$ such distributions.
Four cells each receive two balls and the other four cells each receive one ball: There are $\binom{8}{4}$ ways to select the four cells that each receive four balls, $\binom{12}{2}\binom{10}{2}\binom{8}{2}\binom{6}{2}$ ways to select the balls that will be placed in those cells as we proceed from the leftmost to the rightmost of the four selected cells, and $4!$ ways to distribute the remaining four balls to the remaining four cells so that each cell receives one of those balls. There are $$\binom{8}{4}\binom{12}{2}\binom{10}{2}\binom{8}{2}\binom{6}{2}4!$$ such distributions.
Total: Since these cases are mutually exclusive and exhaustive, there are $$\binom{8}{1}\binom{12}{5}7! + \binom{8}{1}\binom{12}{4}\binom{7}{1}\binom{8}{2}6! + \binom{8}{2}\binom{12}{3}\binom{9}{3}6! + \binom{8}{1}\binom{12}{3}\binom{7}{2}\binom{9}{2}\binom{7}{2}5! + \binom{8}{4}\binom{12}{2}\binom{10}{2}\binom{8}{2}\binom{6}{2}4!$$ ways to distribute $12$ distinct balls to eight cells so that no cell is left empty.
What are you doing wrong?
By designating a particular ball as the ball that is placed in a cell, you count each distribution multiple times, once for each ball you could have designated as the ball that is placed in that cell.
Let's illustrate that point with second case, which you count $4 \cdot 2 = 8$ times. Suppose balls $1, 2, 3, 4$ are placed in cell $A$, balls $5, 6$ are placed in cell $B$, ball $7$ is placed in cell $C$, ball $8$ is placed in cell $D$, ball $9$ is placed in cell $E$, ball $10$ is placed in cell $F$, ball $11$ is placed in cell $G$, and ball $12$ is placed in cell $H$. You count this distribution eight times:
$$ \begin{array}{c c c c c c c c c c} A & B & C & D & E & F & G & H & \text{additional balls in cell $A$} & \text{additional ball in cell $B$}\\ \hline 1 & 5 & 7 & 8 & 9 & 10 & 11 & 12 & 2, 3, 4 & 6\\ 1 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 2, 3, 4 & 5\\ 2 & 5 & 7 & 8 & 9 & 10 & 11 & 12 & 1, 3, 4 & 6\\ 2 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 1, 3, 4 & 5\\ 3 & 5 & 7 & 8 & 9 & 10 & 11 & 12 & 1, 2, 4 & 6\\ 3 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 1, 2, 4 & 5\\ 4 & 5 & 7 & 8 & 9 & 10 & 11 & 12 & 1, 2, 3 & 6\\ 4 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 1, 2, 3 & 5\\ \end{array} $$
By similar reasoning, you count the first case five times, the third case $3 \cdot 3 = 9$ times, the fourth case $3 \cdot 2 \cdot 2 = 12$ times, and the fifth case $2 \cdot 2 \cdot 2 \cdot 2 = 16$ times.
Observe that $$\color{red}{5}\binom{8}{1}\binom{12}{5}7! + \color{red}{8}\binom{8}{1}\binom{12}{4}\binom{7}{1}\binom{8}{2}6! + \color{red}{9}\binom{8}{2}\binom{12}{3}\binom{9}{3}6! + \color{red}{12}\binom{8}{1}\binom{12}{3}\binom{7}{2}\binom{9}{2}\binom{7}{2}5! + \color{red}{16}\binom{8}{4}\binom{12}{2}\binom{10}{2}\binom{8}{2}\binom{6}{2}4! = \color{red}{\binom{12}{8}8!8^4}$$