Throw 7 balls into 7 bins. Given there are exactly 2 empty boxes, find the probability that 1 bin contains 3 balls, and thus the other 4 bins contain 1 ball each.

I know I could use a multinomial distribution to model this problem but I'm confused on how to set it up.


So we are trying to find Pr(2 bins empty & 4 bins have 1 ball each & 1 bin has 3 balls)/ Pr(2 bins are empty).

Pr(2 bins empty) = $7 \choose 2$ $(5/7)(4/7)(3/7)(2/7)(1/7)(5/7)^2$.

Pr(2 bins empty & 4 bins have 1 ball each & 1 bin has 3 balls) = $7 \choose 4$ $3 \choose 2$ $(4/7)(3/7)(2/7)(1/7)(1/7)^3$

Is this reasoning right?

  • $\begingroup$ I think it goes like this $(x^3+x^1+x^1+x^1+x^1+x^0+x^0)^7$ $\endgroup$ – GTX OC Oct 17 '13 at 4:31
  • $\begingroup$ The probability $\Pr(2\text{ bins empty})$ is not correct. You have $\binom72\times5!\times5^2/7^7\approx0.12745$ but it should be $\binom72\times140\times5!/7^7\approx0.7134$ where $140\times5!$ is the number of surjections from agiven $7$-set to a given $5$-set. $\endgroup$ – Marc van Leeuwen Oct 17 '13 at 12:15

Hint: you can ignore the empty bins. How many ways are there to distribute the balls into $5$ bins? I find this one easier if we think the bins and balls are labeled-this is not specified. Then you choose which bin will get the three balls, which three go in that bin, and the arrangement of the other four. How many ways for each of those steps?

  • $\begingroup$ Alright here's what I managed. Please tell me if it's right!. So we are trying to find Pr(2 bins empty & 4 bins have 1 ball each & 1 bin has 3 balls)/ Pr(2 bins are empty). Pr(2 bins empty) = (5/7)^7. Pr(2 bins empty & 4 bins have 1 ball each & 1 bin has 3 balls) = ((1/7)^3)((1/7)^4)(7 choose 3)(4!) $\endgroup$ – Eagle1992 Oct 17 '13 at 4:45
  • $\begingroup$ I was just counting possibilities. The probability of 2 empty is not $(\frac 57)^7$ as you need to choose which two will be empty, then realize you have overcounted the cases where more than two are empty. Since you are given that exactly two are empty, I would define those to be the last two, and the denominator becomes $1$. Please make your reasoning more explicit-maybe edit your question. $\endgroup$ – Ross Millikan Oct 17 '13 at 5:00
  • $\begingroup$ Alright just edited it again. I am pretty sure I got Pr(2 bins empty) right but I'm not 100% sure about the other one. $\endgroup$ – Eagle1992 Oct 17 '13 at 5:28
  • $\begingroup$ Your hint avoids mentioning the trickiest part, which is counting the number of assignments of $5$ bins to the balls that uses each bin at least once. $\endgroup$ – Marc van Leeuwen Oct 17 '13 at 12:56

From the problem statement, one must treat the balls and bins as labelled (our configurations are maps from balls to bins).

The main difficulty in this problem is counting the number ways to get exactly two empty boxes. Since this is about probability, one can simplify by supposing the set of five non-empty bins fixed (the given probability will not depend on which set of five bins this is). So we are given that one of $5$ bins is assigned to each of the $7$ balls, in a surjective way (every bin is used at least once), and within this set we must count the fraction that uses one of the bins three times.

The $5!=120$ permutations of the bins applied to any assignment will always produce $120$ distinct surjective maps (since bins contain disjoint sets of balls, two of them could only contain the same set of balls in the initial assignment if the set were empty, but this does not occur). As this applies both to the set of all surjective maps and to the subset of interest, we may divide out these factors $120$ and consider the bins as unlabelled. Configurations are now determined by the partition of the set of balls into $5$ non-empty sets, and among those we want to count the ones of type $(3,1,1,1,1)$. For the latter there are $\tbinom73=35$ possibilities, determined by the part formed by the $3$ balls. The total number of partitions of our $7$ balls into $5$ non-empty sets is $\genfrac\{\}0{}75=140$, a Stirling number of the second kind. The probability becomes $140/35=1/4$. I think the simplification of the fraction is more or less an accident (although the common prime factor $7$ in numerator and denominator can be explained); the use of Stirling numbers seems unavoidable.

I have avoided computing the number of maps that leave exactly two bins empty. However it can be easily deduced from the above that this number is $\binom75\genfrac\{\}0{}755!$, and the fraction among all maps is $$ \frac{\binom75\genfrac\{\}0{}755!}{7^7}=\frac{35\times140\times120}{7^7} =\frac{5\times20\times120}{7^5}=\frac{12000}{16807}\approx0.7139882. $$


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.