Determine the Probability of no bin being empty when 10 balls are randomly tossed with equal probability into 6 bins

Question

Suppose we have 10 items that we will randomly place into 6 bins, each with equal probability. I want you to determine the probability that we will do this in such a way that no bin is empty. For the analytical solution, you might find it easiest to think of the problem in terms of six events Ai, i = 1, . . . , 6 where Ai represents the event that bin i is empty, and calculate P(AC1 ∩···∩AC6)using DeMorgan’s law.

Analytical= 1- P(bin one empty) + P(bin 2 empty) + P(bin 3 empty) + P(bin 4 empty) + P(bin 5 empty) + P(bin 6 empty) – P(1 and 2 empty) – P(1 and 3 empty) – P(1 and 4 empty) – P(1 and 5 empty) – P(1 and 6 empty) – P(2 and 3 empty) – P(2 and 4 empty) – P(2 and 5 empty) – P(2 and 6 empty) – P(3 and 4 empty) – P(3 and 5 empty) – P(3 and 6 empty) – P(4 and 5 empty) – P(4 and 6 empty) – P(5 and 6 empty) + P( 1 2 3 empty) + P(1 2 4 empty) + P (1 2 5) empty + P (1 2 6 empty) + P( 1 3 4 empty) + P(1 3 5 empty) + P( 1 3 6 empty) + P(1 4 5 empty) + P(1 4 6 empty) + P(1 5 6 empty) – P(1 2 3 4 empty) – P(1235 empty) – P(1236 empty) – P(2345 empty) – P(2346 empty) – P(3456 empty) + P(12345 empty) + P(23456 empty) + P(34561 empty) + P(45612 empty) – P(123456 empty)

1-(6P(1 specific empty bin) – 15P(2 specific empty bins) + 20P(3 specific empty bins) – 15P(4 specific empty bins) +6*P(5 specific empty bins)

This is what I have so far but I don't know how to determine the individual probabilities above.

Answer 1

It can be written as,

$\displaystyle \small 1 - 6 \cdot \bigg(\frac{5}{6}\bigg)^{10} + 15 \cdot \bigg(\frac{4}{6}\bigg)^{10} - 20 \cdot \bigg(\frac{3}{6}\bigg)^{10} + 15 \cdot \bigg(\frac{2}{6}\bigg)^{10} - 6 \cdot \bigg(\frac{1}{6}\bigg)^{10}$

$\displaystyle \small \frac{5}{6}$ represents the probability that an item will land into one of the five specific bins out of six (i.e. a specific bin is empty). Similarly $\displaystyle \small \frac{4}{6}$ represents the probability that an item will land into one of the four specific bins and so on.

Answer 2

Another way is to use Stirling numbers of the second kind which can be conceived as putting n labelled objects (throws $1 \;thru\; 10$) into k identical boxes with no box being left empty. If we multiply $S2(10,6)$ by $6!$ to restore the identity of boxes, we immediately get the answer as $\dfrac{S2(10,6)\cdot 6!}{6^{10}} \approx 0.2718$

---

Addendum

@user2661923 has added a method for manually working out S2(10,6). Here is another way which is totally mechanical, without bothering about double counting. There are $5$ possible templates, viz $511111\;421111\;331111\;322111\;222211$ and the answer is

$10!\left[\dfrac 1 {5!\;5!} + \dfrac 1 {4!2!\;4!}+\dfrac 1 {3!3!\;2!4!}+\dfrac1 {3!2!2!\;2!3!}+\dfrac1 {2!2!2!2!\;4!2!}\right]$

To explain the third template say, to get the arrangements, you want $\binom{10}{3,3,1,1,1,1}\binom{6!}{2!4!}$ which simplifies to $\frac{10!6!}{3!3!1!1!1!1!2!4!}$ but we need to eliminate the $6!$ from the numerator and don't need to pad with $1!$

Answer 3

Addendum added to examine the danger of overcounting from a different perspective.

---

This is a reaction to the answers of Math Lover and true blue anil.

I definitely regard Inclusion-Exclusion as the preferred approach. Math Lover's answer completely covers that.

If you wish to consider the direct approach, then the Stirling Numbers of the Second Kind are dead on point. This is exactly what true blue anil's answer details.

My answer is a manual exploration of what Stirling Numbers of the Second Kind represent, how they are computed, and what their relevance is to this problem.

This Wikipedia Article indicates that :

• $\{ {n\atop k} \} = S(n,k) = $ the number of ways to partition a set of n objects into k non-empty subsets.

• $\displaystyle S(n,k) = \frac{1}{k!}\sum_{i=0}^k (-1)^k \binom{k}{i} (k-i)^n.$

Suppose that you wanted to use the direct approach to the query's problem. Further suppose that you wanted to manually derive each of the numbers, rather than relying on the given formulas. This answer will illustrate the procedure, using the OP's constraints of $(10)$ balls going into $(6)$ rooms, and calculating the probability that each room gets at least one ball.

The probability will be expressed as

$$\frac{N\text{(umerator)}}{D\text{(enominator)}} ~~\text{where}~~ D = 6^{(10)} ~~\text{and}~~ N = N_1 + N_2 + \cdots + N_5.$$

$D = 6^{(10)}$, which was chosen for convenience, represents the total number of ways that each of the $10$ balls might be randomly distributed in the $6$ rooms. Because of this choice, $N$ must be computed in a manner consistent with how $D$ is computed. This means (for example) that [(ball-1 : room-1), (ball-2 : room-2)] must be considered distinct from [(ball-1 : room-2), (ball-2 : room-1)].

There are 5 distinct ways that the 10 balls can be partitioned into 6 non-empty subsets of balls and then distributed into the various rooms. These various ways are enumerated below.

$N_1 : ~~$ 5-1-1-1-1-1
This represents sending $5$ balls into one of the rooms, and $1$ ball into each of the remaining rooms.
There are $\binom{10}{5}$ ways of selecting $5$ balls into 1 unit.
Once this is done, you then have $6$ units that must be distributed into the 6 rooms.
There are $6!$ ways of doing this.

Therefore
$N_1 = \binom{10}{5} \times 6!.$

$N_2 : ~~$ 4-2-1-1-1-1
This represents sending $4$ balls into one of the rooms, $2$ balls into one of the other rooms, and $1$ ball into each of the remaining rooms.
There are $\binom{10}{4} \times \binom{6}{2}$ ways of
selecting $4$ balls into 1 unit and then selecting $2$ balls into another unit.
As before, there are $6!$ ways of distributing the units among the rooms.

Therefore
$N_2 = \binom{10}{4} \times \binom{6}{2} \times 6!.$

$N_3 : ~~$ 3-3-1-1-1-1
Warning - overcounting danger.
Superficially, one would suppose that the enumeration for $N_3$ would be: $\binom{10}{3} \times \binom{7}{3} \times 6!.$

The best way to demonstrate why this is wrong, is by considering a specific example.
Consider sending the units $\{1,2,3\},\{4,5,6\}$ into Room-1 and Room-2, respectively. In one instance, $\{1,2,3\}$ will be the first unit created, $\{4,5,6\}$ will be the second unit created, and the first unit will be sent to Room-1, while the second unit will be sent to Room-2.

In a different instance, $\{4,5,6\}$ will be the first unit created, $\{1,2,3\}$ will be the second unit created, and the first unit will be sent to Room-2, while the second unit will be sent to Room-1.

The overcounting danger is the price you pay for the convenience of using $(6!)$ to enumerate the number of ways of distributing the units into the rooms. As long as you are aware of the danger, there is an easy fix.

By symmetry, because two of the larger units (more than 1 ball) have exactly the same size, you have to apply the scaling factor of $\frac{1}{2!}.$

Therefore
$N_3 = \binom{10}{3} \times \binom{7}{3} \times 6! \times \frac{1}{2!}.$

$N_4 : ~~$ 3-2-2-1-1-1
Again, the scaling factor of $\frac{1}{2!}$ will be needed,
because two of the larger units (more than 1 ball) have exactly the same size.

Therefore
$N_4 = \binom{10}{3} \times \binom{7}{2} \times \binom{5}{2} \times 6! \times \frac{1}{2!}.$

$N_5 : ~~$ 2-2-2-2-1-1
Here, the scaling factor of $\frac{1}{4!}$ will be needed,
because four of the larger units (more than 1 ball) have exactly the same size.

Therefore
$N_5 = \binom{10}{8} \times \binom{8}{2} \times \binom{6}{2} \times \binom{4}{2} \times 6! \times \frac{1}{4!}.$

---

Putting this all together:

$$N ~=~ N_1 + N_2 + N_3 + N_4 + N_5$$

$$=~ 6! \times \left\{\left[\binom{10}{5}\right] ~+~ \left[\binom{10}{4} \binom{6}{2}\right] ~+~ \left[\frac{1}{2!}\binom{10}{3} \binom{7}{3}\right] ~+~ \left[\frac{1}{2!}\binom{10}{3} \binom{7}{2} \binom{5}{2}\right] ~+~ \left[\frac{1}{4!}\binom{10}{2} \binom{8}{2} \binom{6}{2} \binom{4}{2}\right]\right\}$$

$$=~ 6! \times \left[(252) + (3150) + (2100) + (12600) + (4725)\right] ~=~ 6! \times (22827) ~=~ (16435440).$$

---

Addendum
Examine the danger of overcounting from a different perspective.

Consider the subsets that are structured 4-2-1-1-1-1 :
against the subsets structured 3-3-1-1-1-1.

In order for the algorithm to work, each possible subset of the given structure must be counted exactly once.

With the 4-2-1-1-1-1, and the counting algorithm of $\binom{10}{4} \binom{6}{2}$,
the specific collection of subsets
$\{1,2,3,4\}, \{5,6\}, \{7\}, \{8\}, \{9\}, \{10\}$,
will be counted exactly one time.

With the 3-3-1-1-1-1, and the counting algorithm of $\binom{10}{3} \binom{7}{3}$,
the specific collection of subsets
$\{1,2,3\}, \{4,5,6\}, \{7\}, \{8\}, \{9\}, \{10\}$,
will be counted twice.

The first time that it will be counted is when $\{1,2,3\}$ is the first subset formed and $\{4,5,6\}$ is the second subset formed.

The second time that it will be counted is when $\{4,5,6\}$ is the first subset formed and $\{1,2,3\}$ is the second subset formed.

This explains the scaling factor of $\frac{1}{2!}.$

Examining the subsets structured as 2-2-2-2-1-1,
and the counting algorithm of $\binom{10}{2} \binom{8}{2} \binom{6}{2} \binom{4}{2}$
the specific collection of subsets
$\{1,2\}, \{3,4,\}, \{5,6\}, \{7,8\}, \{9\}, \{10\}$,
will be counted (4!) times.

This is because with respect to the counting algorithm, any one of the four 2-element subsets might be created, first. Then, any one of the three other 2-element subsets might be created second, and so forth.

This explains the scaling factor of $\frac{1}{4!}.$

---

One more example:
suppose that instead of forming 10 balls into 6 subsets,
you were forming 10 balls into only 4 subsets.

Consider the subsets structured as 3-3-2-2,
and the counting algorithm of $\binom{10}{3} \binom{7}{3} \binom{4}{2}.$
How many different ways would the following collection of subsets be counted:
$\{1,2,3\}, \{4,5,6\}, \{7,8\}, \{9,10\}$?

The ordering of the creation of the two 3-element subsets could occur in $(2!)$ different ways.
Similarly, the ordering of the creation of the two 2-element subsets could also occur in $(2!)$ different ways.

This means that the correct enumeration for the structure of 3-3-2-2 would be
$\binom{10}{3} \binom{7}{3} \binom{4}{2} \times \frac{1}{2!} \times \frac{1}{2!}.$