1
$\begingroup$

If we throw randomly $n+1$ balls into $n$ bins, what is the probability that exactly two bins are empty?

I tried to do this problem but I didn't get right solution, I would be very grateful if someone would point where am I making mistake, and how should I think about that. Also, if there are any simpler approaches, I would like to see them. I have seen that there have been similar questions but I would really like to find out where my intuition is making mistake.

First case:
$4$ balls inside one bin, and in other bins exactly one ball in each. We have $\binom{n+1}{4}$ ways of choosing $4$ balls from $n+1,$ and we can choose one from $n$ bins. Other balls we can place in $(n-3)!$ ways, so that is finally $n\cdot\binom{n+1}{4}\cdot(n-3)!$ ways. This way $2$ bins stay empty each time.

Second case:
$3$ balls inside one bin, $2$ balls in some other bin, and in left bins $n-4$ balls. I can choose $3$ balls in $\binom{n+1}{3}$ ways and place them into one of $n$ bins, after that I can choose two from $n-2$ left balls in $\binom{n-2}{2}$ ways and place them in one of $(n-1)$ left bins. Considering permutations of balls that I didn't pick, that is finally $\binom{n+1}{3}\cdot n\cdot\binom{n-2}{2}\cdot(n-4)!$ ways. In this case also two bins will be empty.

Third case:
Two bins with two balls in them and other bins with $1$ ball in them, that will also result in $2$ empty bins. Same as described in previous cases, this would be $\binom{n+1}{2}\cdot n\cdot\binom{n-1}{2}\cdot(n-1)\cdot(n-3)! $

Total number of cases is $n^{n+1}.$

Probability is sum of these three cases over total number of cases, but I am making some mistake in counting. Thank you.

$\endgroup$
  • $\begingroup$ Are you certain that your cases are correct? Do you know for sure that all three cases are collectively exhaustive? $\endgroup$ – Frpzzd Jun 14 '17 at 20:43
  • $\begingroup$ "If we throw randomly n+1 balls into n bins" however later on you place 1 ball in each bin leaving you with 1 ball but try to place another 3 to make 4 balls in one bin? ("4 balls inside one bin, and in other bins exactly one ball in each.") am i miss reading the question? $\endgroup$ – Sonny Da Silva-Peters Jun 14 '17 at 20:45
  • 1
    $\begingroup$ The total number of cases is $n^{n+1}$, not $n^{n+2}$. $\endgroup$ – Frpzzd Jun 14 '17 at 20:51
  • $\begingroup$ Yes, if there are 4 balls inside one bin, and one ball in each of other bins, we will always have two bins empty. $\endgroup$ – fzy Jun 14 '17 at 20:54
  • $\begingroup$ I've just edited it, thank you. But still the same question remains. $\endgroup$ – fzy Jun 14 '17 at 20:57
2
$\begingroup$

This is a probability question, so you have a choice of considering ways to arrange indistinguishable balls or ways to arrange balls that are all different. You just have to be consistent in how you add up the probability of each arrangement.

The number of ways to arrange $n+1$ balls (all different) into the $n$ bins is $n^{n+1}.$ All these arrangements are equally likely. The arrangements of indistinguishable balls are not all equally likely, so I will consider the balls all different.

When counting arrangements, you must consider the fact that different choices of which bins are empty will give you different arrangements. I did not see any consideration of that in the question. So for the first case, after choosing one of $n$ bins to put the four balls in, you must choose two of the remaining $n-1$ bins to be empty, so instead of $n\binom{n+1}{4}(n-3)!$ arrangements you have $n\binom{n-1}{2}\binom{n+1}{4}(n-3)!.$ Simplifying this a bit, it is $\frac{1}{48}n(n-1)(n-2)(n+1)!.$

For the second case, you are missing a factor of $n-1$ to account for the number of ways to select the bin to put two balls in, and a factor of $\binom{n-2}{2}$ for the choice of two empty bins, so instead of $n\binom{n+1}{3}\binom{n-2}{2}(n-4)!$ ways you should have $n\binom{n+1}{3}(n-1)\binom{n-2}{2}\binom{n-2}{2}(n-4)!.$ This simplifies to $\frac{1}{24}n(n-1)(n-2)(n-3)(n+1)!.$

For the third case, you actually need to put two balls into each of three bins. But you also need to avoid multiple counting of the same arrangement: for example, choosing bin $1,$ putting balls $1$ and $2$ in that bin, then choosing bin $2$ and putting balls $3$ and $4$ in it, is the same result as choosing bin $2,$ putting $3$ and $4$ in it, then choosing $1$ and putting $1$ and $2$ in it. To avoid double-counting, rather than choosing one bin, then another, then another ($n(n-1)(n-2)$ ways), you can first choose the three bins that will each have two balls ($\binom{n}{3}$ ways) and then fill them left to right. But also remember to choose two empty bins from the remaining $n-3$ before placing the remaining balls. So instead of $\binom{n+1}{2}n\binom{n-1}{2}(n-1)(n-3)!$ you should have $\binom{n}{3}\binom{n+1}{2}\binom{n-1}{2}\binom{n-3}{2}\binom{n-3}{2}(n-5)!.$ This simplifies to $\frac{1}{96}n(n-1)(n-2)(n-3)(n-4)(n+1)!.$

Adding these up, we have $M$ arrangements with exactly two empty bins, where \begin{align} M &= \frac{1}{48}n(n-1)(n-2)(n+1)! + \frac{1}{24}n(n-1)(n-2)(n-3)(n+1)! \\ &\qquad + \frac{1}{96}n(n-1)(n-2)(n-3)(n-4)(n+1)! \\ &= \frac{n(n-1)(n-2)(n+1)!}{96}\left(2 + 4(n-3) + (n-3)(n-4)\right) \\ &= \frac{n(n-1)(n-2)(n+1)!}{96}\left(n^2 - 3n + 2\right) \\ &= \frac{n(n-1)^2(n-2)^2(n+1)!}{96}. \end{align}

And then the probability is just the number of arrangements with exactly two empty bins divided by the total number of arrangements: $$\frac{M}{n^{n+1}} = \frac{(n-1)^2(n-2)^2(n+1)!}{96n^n}. $$

$\endgroup$
  • $\begingroup$ Thank you. Are you sure that for the second case I am missing factor (n-1)? Because I did consider that. And one more question, I can't understand why we choose two empty bins? Wouldn't that be as if we counted that bins are our elementaty cases? Like how many ways we can assign n bins to n+1 balls? But then total number of ways would change? I think this has to do with the first part of your answer, that whatever we choose we have to be consistent with it and we will get the right answer. I think that is giving me trouble. Can you clear it up for me a little bit? Thanks! $\endgroup$ – fzy Jun 15 '17 at 8:01
  • $\begingroup$ You figured out that there were $n$ different bins that could be the one that contains three balls. But three balls in bin 1 and two in bin 2 is a completely different set of arrangements form three balls in bin 1 and two balls in bin 3--that is, it also matters which of the remaining $n-1$ bins gets two balls. That's your factor of $n-1.$ Now suppose we put three balls in bin 1, two in bin 2, and the remaining $n-4$ balls in other bins. The "other" bins could be $3,\ldots,n-2,$ or $4,\ldots,n-1,$ or $3,4,6,\ldots,n,$ etc. $\endgroup$ – David K Jun 15 '17 at 17:48
  • $\begingroup$ Each choice of $n-4$ bins of the remaining $n-2$ gives us a completely different set of arrangements. The number of different choices is "$n-4$ choose $n-2$," but that is equal to "$n-4$ choose $2$"--choose which $n-4$ of the remaining $n-2$ bins should get a ball, or choose which two of them should remain empty, it's really the same set of choices. $\endgroup$ – David K Jun 15 '17 at 17:50
2
$\begingroup$

Not sure what you did wrong, but I suspect that you ignored something in your casework. Also, the total number of cases should be $n^{n+1}$, not $n^{n+2}$. Here is an example of a much simpler approach.

First, calculate the number of ways there can be two empty bins. The number of ways for the two empty bins to be chosen is $$_{n}C_2=\frac{n(n-1)}{2}$$ then, since there must be exactly two empty bins, we must place one ball in each of the remaining $n-1$ bins so that none of them are empty. We then have one last ball with $n-1$ choices. Thus the number of ways to place the balls and have exactly two empty bins is $$\frac{n(n-1)}{2}*(n-1)$$ $$\frac{n(n-1)^2}{2}$$ And so the probability is $$\frac{\frac{n(n-1)^2}{2}}{n^{n+1}}$$ $$\frac{(n-1)^2}{2n^{n}}$$

EDIT: This is incorrect. By saying that the number of ways to distribute the balls is $n^{n+1}$, I imply that the balls are distinct objects; however, if they are distinct, then the number of ways to place one ball in each bin other than the two designated empty bins is $(n-1)!$, and so the number of ways to place the balls and have two empty bins is $$\frac{n(n-1)}{2}*(n-1)!*(n-1)=\frac{n(n-1)^2(n-1)!}{2}$$ and so the probability is $$\frac{\frac{n(n-1)^2(n-1)!}{2}}{n^{n+1}}$$ $$\frac{(n-1)^2(n-1)!}{2n^n}$$

$\endgroup$
  • $\begingroup$ I am sorry but I don't think this is the right answer. $\endgroup$ – fzy Jun 14 '17 at 20:55
  • $\begingroup$ What should the correct answer be? Is this problem from a book? $\endgroup$ – Frpzzd Jun 14 '17 at 20:55
  • $\begingroup$ Yes, the right answer is [(n-1)^2 * (n-2)^2 * (n+1)!]/(96*n^n) $\endgroup$ – fzy Jun 14 '17 at 20:59
  • $\begingroup$ Perhaps the book is also considering the order in which the balls are thrown in the bins? Or maybe the balls count as distinct objects? $\endgroup$ – Frpzzd Jun 14 '17 at 21:02
  • $\begingroup$ I don't think order counts. I just copied problem text. If balls count as distinct objects, how would you do it? $\endgroup$ – fzy Jun 14 '17 at 21:07
1
$\begingroup$

Randomly throw $n$ balls into $m$ bins
means that you consider as equiprobable and indipendent events the
launch the of the $k$-th ball into the $j$-th bin
i.e., a sequence of $n$ independent events, each having $m$ equiprobable results.
Thus the space of elementary events is the $n$D (hyper)cube of side $1\dots m$, containing $m^n$ points (i.e. sequences).
For each launch sequence you are going to construct a histogram of the occupancy level of the bins, as sketched below.
Balls_2_bins_empty-1

Different sequences will provide:
a different occupancy profile, and/or
a different labelling of balls among the bins.
But the order of the labels of the balls within each bin is not taken into consideration (each successive ball can be taken to land over a precedent one, or over a void).

That premised, the number of ways to throw $n$ balls into $m$ bins without restrictions is $m^n$. It includes :
0) the configurations with $0$ empty bins = all bins with at least 1 ball;
1) the configurations with exactly $1$ empty bin, the empty bin being $\{1\},\{2\}, \cdots, \{m\}$;
...
q) the configurations with exactly $q$ empty bins, the empty bins being $\{1,2,\cdots,q-1,q\},\cdots,\{1,2,\cdots,q-1,m\}, \cdots, \{m-q+1,\cdots,m\}$, i.e. all the q-subsets from the set $\{1,\cdots,m\}$;
...
m) the configuration with all $m$ bins empty, which is possible only if $n=0$ (and $0<m$).

Let's call $N(n,m,q)$ the number of configurations with exactly $q$ bins empty, and clearly with the other $m-q$ containing at least one ball.
The number of configurations is the same for each q-subset determined to be left empty, and it is N(n,m-q,0). The number of q-subsets that can be drawn from the set $\{1,\cdots,m\}$ is ${m \choose q}$.

So we can write $$ \bbox[lightyellow] { \left\{ \matrix{ N(n,m,m) = \left[ {0 = n} \right] \hfill \cr N(n,m,q) = \left( \matrix{ m \cr q \cr} \right)N(n,m - q,0) \hfill \cr m^{\,n} = \sum\limits_{0\, \le \,k\, \le \,m} {N(n,m,k)} = \sum\limits_{0\, \le \,k\, \le \,m} {\left( \matrix{ m \cr k \cr} \right)N(n,m - k,0)} \hfill \cr} \right. } \tag{1}$$ where $[P]$ denotes the Iverson bracket $$ \bbox[lightyellow] { \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. } $$

But it is well known that powers, can be transformed into Falling Factorials and thus into Binomial Coefficients, through the Stirling Numbers of 2nd kind, so $$ \bbox[lightyellow] { m^{\,n} = \sum\limits_{0\, \le \,k\, \le \,n} {\left\{ \matrix{ n \cr k \cr} \right\}\,m^{\,\underline {\,k\,} } } \; = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \min \,\left( {n,m} \right)} \right)} {k!\left\{ \matrix{ n \cr k \cr} \right\}\,\left( \matrix{ m \cr k \cr} \right)} = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \min \,\left( {n,m} \right)} \right)} {\left( {m - k} \right)!\left\{ \matrix{ n \cr m - k \cr} \right\}\,\left( \matrix{ m \cr k \cr} \right)} } \tag{2}$$ Because of the symmetry of the Binomial we get the dual representation above, and there cannot be another one relating $m^n$ with ${m \choose k}$. Therefore comparing identity (2) with (1), results in that we shall choose the second one, because we shall have $$ N(n,0,0) = \left[ {0 = n} \right]\quad \quad N(n,n,0) = n! $$

So we conclude that $$ \bbox[lightyellow] { N(n,m - k,0) = \left( {m - k} \right)!\left\{ \matrix{ n \cr m - k \cr} \right\}\quad \Rightarrow \quad N(n,m,0) = m!\left\{ \matrix{ n \cr m \cr} \right\} } $$ and $$ \bbox[lightyellow] { N(n,m,q) = \left( \matrix{ m \cr q \cr} \right)N(n,m - q,0) = \left( \matrix{ m \cr q \cr} \right)\left( {m - q} \right)!\left\{ \matrix{ n \cr m - q \cr} \right\} = {{m!} \over {q!}}\left\{ \matrix{ n \cr m - q \cr} \right\} } \tag{3}$$

so that the answer to your question, in particular, is $$ \bbox[lightyellow] { P(n) = {{N(n + 1,n,2)} \over {n^{\,n + 1} }} = {{n!} \over {n^{\,n + 1} \;2!}}\left\{ \matrix{ n + 1 \cr n - 2 \cr} \right\} } \tag{4}$$

which fully agrees with the answer by David K.

$\endgroup$
  • $\begingroup$ @DavidK: you are totally right, thanks for pointing it out. I amended my answer, which now gives your same results, but expressed in terms of Stirling N. 2nd $\endgroup$ – G Cab Jun 29 '17 at 0:27
0
$\begingroup$

Consider the probability that at least $k$ bins remain empty. Assume we chose some k bins, doesn't matter which ones, thus I won't consider the number of ways to choose $k$ bins. We don't want any balls to enter those k bins. The probability for it is $(\frac{n-k}{n})^{n+1}$, because we want $n-k$ bins (out of $n$ bins) to be hit for $n+1$ times. This ensures that those $k$ will remain empty; but maybe there are some other bins which were not hit by chance. So, this ratio, $(\frac{n-k}{n})^{n+1}$, gives you the probability that at least $k$ bins will remain empty. But you want "exactly $2$ bins" empty. So, I will subtract "the probability of at least 2 bins remain empty" from "the probability that at least 3 bins remain empty" which will result in "the probability that exactly 2 bins remain empty" as you desire. Here is the calculation:

$$(\frac{n-2}{n})^{n+1}-(\frac{n-3}{n})^{n+1}$$ $$\frac{(n-2)^{n+1}-(n-3)^{n+1}}{n^{n+1}}$$ $$\frac{(n-2)^n+(n-2)^{n-1}(n-3)+(n-2)^{n-2}(n-3)^2+...+(n-2)(n-3)^{n-1}+(n-3)^n}{n^{n+1}}$$

$\endgroup$
  • 1
    $\begingroup$ Let $n=3,k=2.$ Write $(a,b,c,d)$ to denote that the first ball went in bin $a,$ the second in bin $b,$ the third in bin $c,$ the fourth in bin $d.$ The ways for at least $k$ bins to be empty are $(1,1,1,1),$ $(2,2,2,2),$ and $(3,3,3,3),$ three ways out of $3^4=81,$ probability $\frac1{27}.$ The formula in this answer gives $\left(\frac{n-k}{n}\right)^{n+1}=\left(\frac13\right)^4=\frac1{81},$ which is one-third of the correct result. I think this answer is incorrect. $\endgroup$ – David K Jun 28 '17 at 0:48
  • $\begingroup$ That was also my initial (wrong) approach to this problem. The matter is that when you have,e.g., at least $1$ bin empty, then the empty could be bin $1$ and , because of the at least , also it can include bin $2$. So the configurations at least $k$ are not mutually exclusive. $\endgroup$ – G Cab Jun 29 '17 at 12:56

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.