How to rigorously interpret and transform "equal chance" in different ways?

Question

Put $100$ identical balls into $10$ identical boxes in a way that each ball enters each box with an equal chance. What's the probability that no box is empty?

I have solved it but like to discuss some concerns in my arguments.

My answer is $\binom{99}{9}/\binom{109}{9}$, i.e., the number of compositions divided by the number of weak compositions. Here I assumed the boxes are ordered/labeled instead of being identical. This should be fine since the probability of "no box is empty" does not depend on whether the boxes are ordered or not. My concern is why each weak composition is equally likely to appear? i.e., how to transform the original assumption that each ball goes to each box with the same probability into the "consequence" that each weak composition will appear with the same probability?

Another question is can we keep the fact that the boxes are the same and do not order them, i.e., both balls and boxes are indistinguishable. Then this problem seems to become the problem of counting integer partitions. The answer seems to be $p_{10}(100)/X$, where $p_{10}(100)$ is the number of ways to write $100$ as a sum of $10$ positive integers (where the order of the summands does not matter), and $X$ is the number of ways to write $100$ as a sum of $10$ non-negative integers (where the order of the summands does not matter). First of all, is there a standard notation for $X$? Secondly, my concern is again whether each partition is equally likely to occur. If this is true, then the two methods should give the same answer.

Answer 1

Putting the $100$ balls randomly in the $10$ boxes is equivalent to choosing randomly a mapping from the set of balls to the set of boxes. There are $10^{100}$ such mappings. The event «no box is empty» occurs when the mapping is a surjection. There are $10!{100\brace 10}$ such surjections where ${\brace}$ is a Stirling number of the second kind. Hence the desired probability \begin{equation} p = \frac{10!}{10^{100}}{100\brace 10}\approx 0.999734 \end{equation} (numerical value by Wolfram Alpha)

Answer 2

First of all, re Stars and Bars Theory, the two methods that you used do give the same answer.

That is $p_{10}(100)$ bijects to determining the number of non-negative integer solutions to $x_1 + \cdots + x_{10} = 90.$ So, both methods do yield

$$\frac{\binom{99}{9}}{\binom{109}{9}}. \tag1 $$

Despite that, the answer in (1) above is still wrong. The point is that, as you indicated, each individual solution to (for example) $x_1 + \cdots + x_{10} = 100$ is not equally likely to occur.

---

Edit
Actually, my analysis of the two approaches taken by the OP (i.e. Original Poster) was careless. In his 2nd approach, he specifically assumed that the boxes were to be regarded as indistinguishable. So, my analogy of (for example) enumerating the number of positive integer solutions to $x_1 + \cdots + x_{10} = 100$ is not valid.

Just to emphasize the point that even regarding the boxes as indistinguishable is still the wrong way to go, consider the following simplification.

Suppose that you have $6$ balls to be distributed to $3$ blns, and let $(b_1, b_2, b_3)$ denote a solution where bin-1 receives $b_1$ balls, bin-2 receives $b_2$ balls, and bin-3 receives $b_3$ balls.

Consider the various solutions to $b_1 + b_2 + b_3 = 6.$

First, assume that the bins are distinguishable. Then, there are $~\displaystyle \binom{6}{2}\binom{4}{2} = 90~$ distinct ball distributions that are represented by the $(2,2,2)$ solution and $~\displaystyle \binom{6}{3}\binom{3}{2} = 60~$ distinct ball distributions that are represented by the $(3,2,1)$ solution.

So, the $(2,2,2)$ and $(3,2,1)$ solutions do not represent an equal number of ball distributions into the bins.

Now, consider what happens if an attempt is made to construe the bins as indistinguishable. It is as if the bins were first labeled, the balls were distributed to the bins, and then the labels were removed from the bins.

With the bins being considered indistinguishable, the $(2,2,2)$ solution only represents $(b_1,b_2,b_3) = (2,2,2)$. In contrast, the $(3,2,1)$ solution actually represents $(b_1, b_2, b_3)$ being any element in

$$\{(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)\}.$$

So, by construing the bins as indistinguishable, and then enumerating the different partitioning possibilities, you have that the two partitioning solutions of $(2,2,2)$ and $(1,2,3)$ actually represent distributions sets whose sizes are in the proportions of $[90::360]$.

This means that if you are going to enumerate the partitions, where the bins are considered distinguishable, then the $(2,2,2)::(1,2,3)$ solutions must be given relative weights of $[90::60]$.

If instead, you enumerate the partitions where the bins are considered indistinguishable, then the $(2,2,2)::(1,2,3)$ solutions must be given relative weights of $[90::360]$.

---

Another approach that is no good is

$$1 - \frac{\binom{10}{1}\times (9)^{(100)}}{(10)^{(100)}}. \tag2 $$

The flawed idea re (2) above is that in the numerator, first you select a bin to be left empty. Then, each of the $(100)$ balls has $9$ choices for the other bins. The reason that (2) above is no good is because of over-counting. That is, if you leave bin-1 empty, included in the $(9)^{(100)}$ computation will be occurrences where bin-2 was left empty. So, the times when bin-1 and bin-2 are both left empty is counted twice.

---

It is unclear to me whether there is an elegant approach that involves either direct computation, recursion, or generating functions. My go-to strategy, in this situation, is Inclusion-Exclusion.

See this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula.

I am going to adopt the syntax of the 2nd link above.

---

$T_0$ will equal $(10)^{(100)}$, which will also serve as the denominator, just as it did in (2) above.

Let $S$ denote the set of all possible distributions of the balls into the $10$ bins. Then, $|S| = T_0$.

For $k \in \{1,2,\cdots,k\}$, let $S_k$ denote the subset of $S$, where bin-k was left empty.

Then, the desired computation will be

$$\frac{|S| - |S_1 \cup \cdots \cup S_k|}{|S|}. \tag3 $$

---

Let $T_1$ denote $|S_1| + \cdots + |S_{10}|.$

For $r \in \{2,3,\cdots,10\}$,

let $T_r$ denote $~\displaystyle \sum_{1 \leq i_1 < i_2 < \cdots < i_r \leq 10} |S_{i_1} \cap S_{i_2} \cap \cdots \cap S_{i_r}|.$

That is, $T_r$ represents the sum of $~\displaystyle \binom{10}{r}$ terms.

Then, in accordance with Inclusion-Exclusion Theory, the desired computation, which is represented in (3) above, will equal

$$\frac{\sum_{r=0}^{10} (-1)^r T_r}{T_0}, \tag4 $$

where $~\displaystyle T_0 = (10)^{(100)}.$

So, in order to resolve (4) above, all that remains is to evaluate $T_1, T_2, \cdots, T_{10}.$

---

$\underline{\text{Computation of} ~T_1:}$

$\displaystyle |S_1| = 9^{(100)}.$

By reasons of symmetry, $|S_1| = |S_2| = \cdots = |S_{10}|.$

Therefore,

$$T_1 = \binom{10}{1} 9^{(100)}. \tag5 $$

---

$\underline{\text{Computation of} ~T_2:}$

$\displaystyle |S_1 \cap S_2| = 8^{(100)}.$

By reasons of symmetry, for any $i,j \in \{1,2,\cdots,10\} ~: i \neq j$,

you have that $|S_i \cap S_j| = |S_1 \cap S_2|.$

Therefore,

$$T_2 = \binom{10}{2} (10-2)^{(100)}. \tag6 $$

---

$\underline{\text{Computation of} ~T_r: 3 \leq r \leq 9}$

$\displaystyle |S_1 \cap S_2 \cap \cdots \cap S_r| = (10-r)^{(100)}.$

By reasons of symmetry, there will be $~\displaystyle \binom{10}{r}~$ identical terms.

Therefore,

$$T_r = \binom{10}{r} (10-r)^{(100)}. \tag7 $$

---

$\underline{\text{Final Computation}}$

Clearly, $T_{10} = 0$, because it is impossible to distribute the $(100)$ balls into the bins, with the result that all of the bins are empty.

Therefore, the final computation is

$$\frac{(10)^{(100)} + \sum_{r=1}^{9} \left[(-1)^r \times \binom{10}{r} \times (10-r)^{(100)}\right]}{(10)^{(100)}}.$$