# Colored Bins and Colored Balls

Suppose we have N different colors bins. Each bin can only hold B balls. Suppose we have N*B balls such that for each bin n we have B balls of the same color as this bin. Therefore in total we have N*B balls.

What is the probability that for a given bin I it contains a ball the same color as itself?

I got B/N*B = 1/N.

Hint: First distribute the balls of color $A$, and then distribute the remaining balls. (This is exactly the same (probabilistically) as uniformly distributing all the balls at once).

The probability that bin $A$ \emph{does not} have a ball of color $A$ is the probability that all $A$ balls are distributed into the remaining $N-1$ bins. What is this probability?

• From what I gather, the total combinations must be B*N! / B!^{N}. Also, if A balls are distributed into the remaining N-1 bins, then we have (B*(N-1) choose B)(B*(N-1)! / B!^{N-1}) ways of doing this. Am I on the right track here? – J. Doe Sep 19 '18 at 5:13

Let's assume the balls of the same color are distinguishable (you may mark them black 1, black 2, ... black B etc). The difference between distinguishable and non-distinguishable does not matter much here. I just find it easier to explain in the distinguishable case and you may come up with a similar argument with the non-distinguishable case.

Another assumption is each ball configuration is equiprobable. There are all together $(NB)!$ configurations. Each such configuration has probability $\frac{1}{(NB)!}$

Suppose you have picked the bin A. Imagine you are filling this bin A first, and then the other bins. The number of ways to fill bin A will be $(NB)(NB-1)\cdots(NB-B+1)$. The number of ways to fill bin A without balls of the same color as bin A will be $(NB-B)(NB-B-1)\cdots(NB-2B+1)$. So the probability of filling bin A without balls of the same color as bin A is $\frac{(NB-B)(NB-B-1)\cdots(NB-2B+1)}{(NB)(NB-1)\cdots(NB-B+1)}$.

And the probability of filling bin A with at least one ball the same color as bin A is $1-\frac{(NB-B)(NB-B-1)\cdots(NB-2B+1)}{(NB)(NB-1)\cdots(NB-B+1)}$.

• To make it even more explicit, let's say bin A is Red. There are all together $(NB)!$ configurations. The number of configurations without any Red balls in bin A is $[(NB-B)\cdots(NB-2B+1)]\ [(NB-B)!]$. The first part, $[(NB-B)\cdots(NB-2B+1)]$, is the number of ways to fill the $B$ positions of bin A with the $NB-B$ non-Red balls. The second part, $(NB-B)!$, is the number of ways to fill all other bins with the remaining $NB-B$ balls. So the probability is given by $\frac{[(NB-B)\cdots(NB-2B+1)]\ [(NB-B)!]}{(NB)!} = \frac{(NB-B)\cdots(NB-2B+1)}{(NB)\cdots(NB-B+1)}$. – William Wong Sep 19 '18 at 6:07
• What if N= 1 and B = 2? Then your formula gives undefined value. – J. Doe Sep 20 '18 at 14:36
• Whenever N=1 (and whatever B is), you take that a special case. The probability of filling bin A with same color ball is just 1. – William Wong Sep 20 '18 at 17:46

There are about $\frac {(NB)!}{(N!)^{B}(B!)^N}$ arrangements. First number all the balls. You can think of lining up all the balls, which gives $(NB)!$ possibilities. There are $N!$ ways to rearrange the balls within one bin and $B!$ ways to rearrange the balls of each color, giving equivalent distributions. It is not quite right because if two balls of the same color are in a bin we overcount the number of rearrangements.

The number of orders that do not have any balls of color $1$ in bin $1$ has the first $N$ factors of the numerator reduced by $N$ because we can't choose any balls of that color. The reduction is then a factor $$\frac {(NB-N)(NB-N-1)(NB-N-2)\ldots (NB-2N+1)}{(NB)(NB-1)(NB-2)\ldots (NB-N+1)}=\frac {(NB-N)!(NB-N)!}{(NB)!(NB-2N)!}$$ This is a job for Stirling's approximation, which makes it $$\frac {(NB-N)^{2(NB-N)}}{(NB)^{NB}(NB-2N)^{NB-2N}}\sqrt{\frac {(NB-N)(NB-N)}{(NB)(NB-2N)}}$$ The square root is very close to $1$ and I will ignore it. We can pull out all the $N$s and get $$\frac {(B-1)^{2(NB-N)}}{(B)^{NB}(B-2)^{NB-2N}}=\left(1-\frac 1{B-2}\right)^{NB}\left(1+\frac 1B\right)^{NB-2N}=\left(1-\frac 1{B-2}\right)^{2N}\left(1-\frac 2{B(B-2)}\right)^{NB-2N}$$

• That the balls are non-distinguishable does not matter much, so long as you follow through the deviation. For non-distinguishable balls, the totally number of arrangements is $\frac{(NB)!}{(B!)^N}$ (not $\frac{(NB)!}{(N!)^{2B}}$ as you mentioned above). But the same factor $(B!)^N$ has to be applied to the numerator when you compute the probability, so it just cancel out, and you will have the same final answer. – William Wong Sep 19 '18 at 5:56
• @WilliamWong: I think the denominator should be $(B!)^N(N!)^B$ because of the two reorders I mention. I agree it doesn't factor into the second paragraph and on. – Ross Millikan Sep 19 '18 at 13:52
• Ross, what if N = 1 and B = 2? Your formula gives an undefined value. – J. Doe Sep 20 '18 at 12:56
• @J.Doe: Stirling's approximation assumes the number you are taking the factorial of is large. It is already good at $4$, where it returns $23.5$ compared to $24$, but below that is not so good. If there is only one bin, the probability is $0$ – Ross Millikan Sep 20 '18 at 15:15