# Dividing colored balls between children

The following was an exercise I solved:

We have 8 numbered balls - two blue, two red, two green, and two yellow. When dividing them between 4 children, 2 balls each, what is the probability at least one child will get two balls of the same color?

I solved it using the exclusion-inclusion principle, and got the end result $3/7$. My question is, since this is such a nice fraction, was there any way of solving the problem such that I could've arrived at the fraction directly?

(This is the calculation I did: http://www.wolframalpha.com/input/?i=C(4%2c1)*(4*C(6%2c2)*C(4%2c2)C(2%2c2))%2f2520-C(4%2c2)(4*3*C(4%2c2)C(2%2c2))%2f2520%2bC(4%2c3)(4*3*2*C(2%2c2))%2f2520-C(4%2c4)*(4*3*2*1)%2f2520&incParTime=true)

-
I'm sorry, I forgot to mention each child gets exactly 2 balls. – roel Nov 12 '11 at 18:17

I don't think there is a one-line computation of this probability or its complement; but you can do without the inclusion-exclusion principle. In order to compute the probability $p$ that no child receives two balls of the same color one may argue as follows:

At the beginning the eight balls are in an urn. The first child has 28 possibilities of drawing two balls without replacement, 4 of which are bad. Therefore we have a probability of ${6\over7}$ that the first child gets two balls of different colors, say $\{a,b\}$.

The six balls left have a color distribution $\{a,b,c,c,d,d\}$. The second child has 15 possibilities of drawing two balls out of these, 2 of which are bad. With probability ${1\over15}$ she picks $\{a,b\}$. The remaining four balls $\{c,c,d,d\}$ admit three pairings, and one of these is bad. With probability ${2\cdot 4\over15}$ the second child picks $\{a,c\}$ (or similar). The remaining four balls $\{b,c,d,d\}$ again admit three pairings, one of them bad. Finally, with probability ${2\cdot 2\over15}$ the second child picks $\{c,d\}$, in which case four balls of different colors remain which can be paired in any way.

Putting it all together we see that the probability $p$ is given by $$p\ =\ {6\over7}\cdot\Biggl({1\over15}\cdot{2\over3}+{8\over15}\cdot{2\over3}+{4\over15}\cdot1\Biggr)={4\over7}\ .$$

-

It is easier to calculate the complement - that each child gets at most 1 ball. For the first ball the chance is 1, for the second $\frac{n-1}{n}$

You get for k balls and n (>k) children $\frac{n!\cdot (n-k)!}{n^k}$

-
I'm sorry, I forgot to mention each child gets exactly 2 balls. – roel Nov 12 '11 at 18:17

This problem depends on whether we can tell the difference between two balls of the same color. (And whether you can tell the difference between two children, but I'm assuming that's so.) Your statement doesn't make clear which case you're looking at. Unfortunately, I'm having trouble coming up with an elegant solution in either case, but I have some comments.

(1) Balls of the same color are distinguishable. Here, the space of possibilities has size equal to the number of ways to choose four pairs of balls (that's given by the multinomial coefficient $\binom{8}{2,2,2,2} =\frac{8!}{(2!)^4} = 2,520$) multiplied by the number of ways of distributing those four pairs to the four children (which is just $4! =24$). So the space has size 60,480. If you reason along similar lines to compute the number of ways to distribute balls so that at least one child gets two balls of the same color you'll wind up doing some double-counting so I think some kind of inclusion-exclusion is necessary.

(2) Balls of the same color are not distinguishable. The number of ways to distribute the balls here so that no child gets two balls of the same color is equal to the number of 2-regular bipartite graphs where the vertex set is bipartitioned into two sets of four vertices and with no multiple edges. An edge $(i,j)$ in such a graph means that child $i$ gets a ball of color $j$. The fact that it's 2-regular means every child gets exactly two balls and that there are two balls of each color. The size of the bipartition means that there are four children and four types of balls. Similarly, the total number of ways to distribute the balls is equal to the same number of graphs, but where we allow multiple edges. I know of no formulas to compute either quantity in general, though.

-