Probability – Different Approaches to N Balls and M Boxes Problem

Question

Suppose that you have N indistinguishable balls that are to be distributed in m boxes (the boxes are numbered from 1 to m). What is the probability of the i-th box being empty (where the i-th box is the box with the number i) given that the balls have equal chances of arriving at any box?

I found two different approaches to solve this problem (which I post bellow). Since each of them leads to a different solution, I am having a hard time trying to find which one is incorrect. I am fairly sure that the first approach is correct since it follows the 'standard' way of solving problems involving indistinguishable balls, but I cannot find the error in the second one. I would greatly appreciate any help you could provide to solve this doubt.

(1) First approach: (Bosons) The number of ways of distributing N indistinguishable balls into m boxes is equal to: $$\binom{N + m -1}{N}=\frac{(N + m – 1)!}{N!(m-1)!} $$ On the other hand, the number of ways to distribute the balls and leaving the i-th box empty can be obtained by leaving the i-th box empty and distributing the N balls into the remaining m – 1 boxes. This is equal to: $$\binom{N + m – 2}{N}=\frac{(N + m – 2)!}{N!(m-2)!}$$ Therefore the probability of the i-th box being empty is the quotient of the second number by the first: $$\frac{(N + m – 2)!}{N!(m-2)!}.\frac{N!(m-1)!}{(N + m – 1)!}=\frac{m-1}{N + m – 1}$$
(2) Second approach: (Counting functions) Suppose that before distributing the balls into the boxes we number them from 1 to N. Then for each ball, the number of ways of distributing that ball into the m boxes is m. So the number of ways to distribute N balls into m boxes is: $$m^N$$ If we want to distribute N numbered balls into m boxes leaving the i-th box empty, each ball can only go to the m-1 remaining boxes. Therefore the number of ways in which this can be done is: $$(m-1)^N$$ And the desired probability will be the quotient: $$\left(\frac{m-1}{m}\right)^N \neq \frac{m-1}{N + m – 1}$$

Thank you very much for your time.

Answer 1

Note: The formulation of this question has to be considered carefully in order to find the correct approach.

The situation describes $N$ indistinguishable balls which are to be distributed in $m$ distinguishable boxes.

Looking at a simple example as suggested by @MickA is often a good starting point. Let's have a look at an example with $N=2$ indistinguishable balls and $m=2$ distinguishable boxes. So, after distributing the $2$ balls into the $2$ boxes, we can see one of three possible outcomes:

\begin{array}{rcl} \text{Box $1$} &|& \text{Box $2$} \\ \hline \bullet\;\bullet &|& \\ \bullet &|& \bullet \\ &|&\bullet\; \bullet \end{array}

We observe, if the question would have asked for something like

• number of possible outcomes or

• number of different configurations

The Ansatz would be according to the first approach

\begin{align*} \binom{N+m-1}{N}\tag{1} \end{align*}

which respects the fact that the balls are indistinquishable and the boxes are distinguishable.

But this is not the question! The crucial text is:

... given that the balls have equal chances of arriving at any box.

Therefore we have to count the number of possible arrivals

\begin{array}{rclcc} \text{Box $1$} &|& \text{Box $2$} &|& \text{Nr of possibilities}\\ &|& &|& \text{to reach this configuration}\\ \hline \bullet\;\bullet &|& &|& 1\\ \bullet &|& \bullet &|& 2\\ &|&\bullet\; \bullet&|& 1 \end{array}

We see, counting the number of possibilities or equivalently calculating the corresponding probabilities

\begin{array}{rclcc} \text{Box $1$} &|& \text{Box $2$} &|& \text{probability}\\ &|& &|& \text{to reach this configuration}\\ \hline \bullet\;\bullet &|& &|& 0.25\\ \bullet &|& \bullet&|& 0.50\\ &|&\bullet\; \bullet&|& 0.25 \end{array}

is a different situation than (1) leading to the second approach

$$m^N$$

Result:

Therefore, we finally get the probability:

$$\left(\frac{m-1}{m}\right)^N$$