Suppose I have $n$ boxes, and $n^2$ balls, of which $b$ are colored blue. Each box has a capacity of holding $n$ balls. If I randomly assign balls to boxes until all the balls are placed, what is the probability that each box has at least one blue ball?

I've been working on this for small cases. Suppose $n = b = 3$. There should be ${9}\choose{3}$ ways to place the blue balls, and $3^3$ of these will result in one in each box, so the probability is $\frac{27}{84}$. If I add a fourth blue ball I see 6 places it could go, but if there are 2 blue balls in the same box, that would give me some overcounting, so I end up with $3^4$ ways to get at least one blue in each box. For 5 balls I brute-forced it, and ended up with $\frac{3^3\cdot 4}{{9}\choose{5}}$ for the probability. I haven't been able to come up with a good counting scheme to explain why this is true, and am unable to generalize.

  • $\begingroup$ Are other balls all differently colored? $\endgroup$ – Archis Welankar Jun 24 at 13:45
  • $\begingroup$ @ArchisWelankar, the balls that are not blue are all the same color $\endgroup$ – Jeff Ford Jun 24 at 13:51
  • $\begingroup$ I don't understand your $n=b=3$ example. As I see it, If we count only the blue balls configurations, the successful configurations are $3!$ and the total configurations are $3^3$ hence the probability is $2/9$. Could you explain ? $\endgroup$ – leonbloy Jun 25 at 3:33
  • $\begingroup$ @leonbloy if you have 3 boxes of capacity 3, there are 9 spots to put a ball, and 3 balls, hence ${9}\choose{3}$ is the denominator. If you want to put one blue into each box you have 3 spots of capacity in the first box, 3 in the second and 3 in the third. If you're just putting them in randomly, you need to choose one of the 3 spots from each to avoid 2 blues in the same box, so the numerator is $3^3$. $\endgroup$ – Jeff Ford Jun 25 at 15:15
  • $\begingroup$ " there are 9 spots to put a ball" So in you thinking a box with "capacity" 3 has 3 different "places", so there are three different ways of placing a single blue ball that into box 1? That's a rather non-standard way of interpreting the problem statement, I think you should be more crear about this and check if the current answer take this into account. $\endgroup$ – leonbloy Jun 25 at 18:04

Number the boxes and for $i=1,\dots, n$ let $E_i$ be the event that box $i$ does not contain a blue ball.

Then with inclusion/exclusion and symmetry we find: $$1-P\left(\bigcup_{i=1}^{n}E_{i}\right)=\sum_{k=0}^{n}\binom{n}{k}\left(-1\right)^{k}P\left(\bigcap_{i=1}^{k}E_{i}\right)=\binom{n^{2}}{b}^{-1}\sum_{k=0}^{n}\binom{n}{k}\left(-1\right)^{k}\binom{n\left(n-k\right)}{b}$$

This under the conventions that $\binom{r}{s}=0$ if $s\notin\{0,1,\dots,r\}$ and $\cap\varnothing=\Omega$ (so that $P(\cap\varnothing)=1$).

  • $\begingroup$ Thanks, this is what I was looking for! Now I just need to figure it out when each box has a different capacity. If each box has capacity $c_k$, then the $n^2$ should just be replaced by $\prod c_k$, but I'll have to think about how the rest of the value change. $\endgroup$ – Jeff Ford Jun 24 at 19:31
  • 1
    $\begingroup$ By different capacities the principle of inclusion/exclusion can still be applied, but not symmetry. A term on RHS (in my answer) starting with $\binom{n}{k}$ will become a summation of $\binom{n}{k}$ terms. $\endgroup$ – drhab Jun 25 at 8:49
  • $\begingroup$ Does this give the OP's desired value for $n=b=3$ ? $\endgroup$ – leonbloy Jun 25 at 18:08
  • $\begingroup$ @leonbloy Yes, it does. $\endgroup$ – drhab Jun 25 at 18:25

You can consider the "non-blue" balls as "voids": that means that the problem boils down to how to place $b$ balls into $n$ boxes of capacity $n$, such that there is at least one (blue) ball in each box.

So you are looking for $$ \eqalign{ & N_b (b - n,n - 1,n) = \cr & = {\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm 1} \le {\rm integer}\;x_{\,j} \le n \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,n} = b \hfill \cr} \right. = \cr & = {\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ 0 \le {\rm integer}\;y_{\,j} \le n - 1 \hfill \cr y_{\,1} + y_{\,2} + \; \cdots \; + y_{\,n} = b - n \hfill \cr} \right. \cr} $$ which, as explained in this related post is given by $$ \eqalign{ & N_b (b - n,n - 1,n)\quad \left| \matrix{ \;{\rm integers }b,n \hfill \cr \;1 \le n \le b \hfill \cr} \right.\quad = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{{b - n} \over n}\, \le \,n} \right)} {\left( { - 1} \right)^k \left( \matrix{ n \cr k \cr} \right)\left( \matrix{ b - 1 - k\,n \cr b - n - k\,n \cr} \right)} \cr} $$


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.