Distribute 10 white and 10 black balls into 20 distinct boxes s.t. no box is empty?

How many ways are there to distribute 10 white and 10 black balls into 20 distinct boxes such that no box is empty?

Solution is that ${20!}/{10!10!}$. How can we write this? Please can you explain this solution clearly?

-

2 Answers

There are several ways to see it. The one that I find easiest is to notice that once we choose which $10$ boxes get white marbles, we’ve specified the entire distribution: the black marbles have to go into the remaining $10$ boxes. Thus, there is one distribution for each possible way of choosing $10$ of the $20$ boxes to contain the white marbles. There are $\binom{20}{10}$ ways to choose $10$ things out of a set of $20$, so there are $$\binom{20}{10}=\frac{20!}{10!10!}$$ possible distributions.

Another way is to start by pretending that the $20$ marbles are labelled, say $W_1$ through $W_{10}$ for the white marbles and $B_1$ through $B_{10}$ for the black marbles.. There are then $20!$ distinguishable permutations of these $20$ marbles. However, the marbles aren’t actually labelled. Pick any distribution, and focus on the white marbles. We could rearrange them as we please, so long as we leave the black marbles in place, and the resulting distribution would be indistinguishable from the one we started with. There are $10!$ ways to arrange the $10$ white marbles in those same $10$ positions; we’ve counted them all separately, but in fact they’re all the same arrangement of colors. Thus, we’ve overcounted by a factor of $10!$. If we divide by $10!$ to correct for the overcounting, we get $\frac{20!}{10!}$, which is the number of arrangements if the white marbles are indistinguishable, but the black marbles bear individual labels so that we can tell them apart.

In fact the black marbles bear no such labels. We’ve counted each set of $10$ positions for the black marbles once for every permutation of the black marbles in those positions, so we’ve overcounted by another factor of $10!$. Dividing by $10!$ to compensate finally gives us the correct answer for the unlabelled marbles:

$$\frac{20!}{10!10!}\;.$$

-

There are $20$ boxes and $20$ balls in total, so each box must receive exactly one ball. The question is reduced to choosing which $10$ boxes get black balls and which $10$ get white balls, which is equivalent to choosing $10$ boxes to put the black balls in and filling the rest with white balls. The number of ways to choose $10$ boxes out of $20$ is $${20 \choose 10} = \frac{20!}{10!\cdot 10!},$$ which is the answer.

-
Thx @ybungalobill –  B11b Dec 25 '12 at 18:10