1
$\begingroup$

In how many ways can I give out n white balls(identical), and n colored balls(different colors), to 2n boxes so that in each box:

1) at most one ball

2) at most one white ball(there can be several colored balls)

3) at most one colored ball(there can be several white balls)

4) equal number of white and colored balls

$\endgroup$
0
$\begingroup$

Hints:

1) So everybody gets exactly one ball. Label the colours $C_1$ to $C_n$. The ball $C_1$ can be assigned in $2n$ ways. For each such way, the ball $C_2$ can be assigned in $2n-1$ ways. And so on.

2) Ball $C_1$ can be assigned in $2n$ ways. For each such way, ball $C_2$ can be assigned in $2n$ ways. And so on. For every way of assigning the coloured balls, how many ways are there to choose the boxes that will receive a white?

3) Count the number of ways to assign the coloured balls. We have already mentioned how to find this. For each way, how many ways are there to assign the whites? (This component of the calculation is done using Stars and Bars.)

4) The only thing that matters is the coloured balls.

Added Detail:

For 1), the coloured balls are all distinct. The ball coloured $C_1$ can be put in any one of the $2n$ boxes. A box can contain at most one ball. So for every way of assigning a box to ball $C_1$, there are $2n-1$ ways to assign a box to ball $C_2$. And now there are $2n-2$ ways to assign a box to ball $C_2$, and so on.

Thus there are $(2n)(2n-1)(2n-2)\cdots(2n-n+1)$ ways to assign boxes to all the coloured balls. If you wish, this number can be written alternately as $\frac{(2n)!}{n!}$. Once we have assigned boxes to the coloured balls, there is only one way to assign boxes to the white balls, since every box is supposed to hold exactly one ball. Thus the answer to 1) is $\frac{(2n)!}{n!}$.

One can do problem 1) in other ways. For example, we can choose which boxes will hold white balls. This can be done in $\binom{2n}{n}$ ways. For every way of deciding which boxes hold white balls, the remaining $n$ coloured balls can be assigned to the remaining $n$ boxes is $n!$ ways. That gives a total of $\binom{2n}{n}n!$, which can be simplified in various ways, for example to $\frac{(2n)!}{n!}$.

For problem 2), there are no restrictions except that a box can contain at most one white. So ball $C_1$ can be assigned a box in $2n$ ways. Since a box can hold more than one coloured ball, the ball $C_2$ can now be assigned a box in $2n$ ways, and so on for a total of $(2n)^n$ ways. For every one of these ways, we can choose the boxes that will hold a white ball in $\binom{2n}{n}$ ways, for a total of $(2n)^n \binom{2n}{n}$.

$\endgroup$
  • $\begingroup$ I looked at the answers but the hints don't give me any progress towards them. $\endgroup$ – user113977 Dec 28 '13 at 21:05

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.