2
$\begingroup$

in how many ways $n$ white (identical ) balls and $n $ colorful (n different colors) balls can be placed in $2n $ cells such that in each cell: $$$$a. at the most one ball. answer $_{2n}C_n\cdot n!$ how does the fact of "at most" shown here? $$$$b. at the most one white ball but can be several colorful. answer: $_{2n}C_n\cdot(2n)^n$ why does $(2n)^n$ mean several balls? $$$$c. at the most one colorful ball but can be several white answer: $_{2n}C_n\cdot n!\cdot(_{2n+n-1}C_n)$ why not $_{2n}C_n\cdot n!\cdot(_{2n+n-1}C_{n-1})$ isn't it nSk case ? and it seems to have different principal then that of b, may you explain this expression? $$$$d.equal number of colorful and white answer: $(2n)^n$why?doesn't this exportation would mean in each cell unlimited number of balls?

$\endgroup$
  • $\begingroup$ Care to share your own ideas on how to answer the "why?"s, or if you think they are right or not? $\endgroup$ – vonbrand Feb 7 '14 at 0:38
  • 2
    $\begingroup$ Hint: If each cell has at most $1$ ball, and there are $2n$ balls and cells, then each cell must have exactly one ball. $\endgroup$ – MCT Feb 7 '14 at 0:45
3
$\begingroup$

For (a), as you have $2n$ balls and $2n$ cells, "at most one ball in each cell" is the same as "exactly one ball in each cell". So

(1) Choose $n$ cells for the white balls. . . . . $C(2n,n)$ ways

(2) Order the coloured balls in the remaining $n$ cells. . . . . $n!$ ways.

Answer, $C(2n,n)n!$ ways.

For (b), the coloured balls can go in cells with a white ball, or with other coloured balls... in other words they can go anywhere:

(1) Choose $n$ cells for the white balls. . . . . $C(2n,n)$ ways

(2) For each coloured ball there are $2n$ choices. . . . . $(2n)^n$ ways.

Total, $C(2n,n)(2n)^n$ ways.

For (d), the coloured balls can go anywhere, as in (b). After doing this, each cell must be "filled up" with the same number of white balls as coloured balls. So there is only one option for the white balls. Answer, $(2n)^n$ ways.

For (c):

(1) Choose $n$ places for the coloured balls. . . . . $C(2n,n)$ ways.

(2) Order the balls in these places. . . . . $n!$ ways.

(3) Place white balls, see below. . . . . $C(3n-1,n)$ ways.

Total, $C(2n,n)\,n!\,C(3n-1,n)$ ways.

You can argue (3) as follows. Ignore the coloured balls and think of the white balls. You can picture the arrangement as a row of $n$ white balls, with lines between to show which go in which cells. For example, $${\tt 0|0||0|000|}$$ represents one ball in the first cell, one in the second, none in the third, one in the fourth, three in the fifth and none in the sixth. If there are $2n$ cells there will be $2n-1$ lines (and $n$ balls). So the problem is equivalent to choosing which $n$ of $3n-1$ locations are to take the balls. Note that we are not choosing balls, or lines, or cells, but locations.

$\endgroup$
2
$\begingroup$

Note that the notation $n \choose r$ is euivalent to $_n C_r$ (and is more widely used).

a. Then each urn most have exactly one ball. First we have to choose which urns hold colorful balls and which urns hold white balls, which would be ${2n \choose n}$. Then we count the number of permutations of the different colors, which would be $n!$, giving a total of $n! {2n \choose n}$.

b. Consider white and colored balls separately. We can choose which urns get a white ball in ${ 2n \choose n}$ ways. Then for each colored ball, we have $2n$ choices for where to put them, which would be represented by $(2n)^n$, which explains the given answer.

c. The first part is like a. in that each urn has at most one colored ball, so there are $n! {2n \choose n}$ ways to do that as said before. The next part is related to the theorem of "balls and urns," saying that the number of ways to give $n$ indistinct things to $k$ distinct destinations is ${n+k-1 \choose n}$.

d. If there is an equal number of white and colored balls, we can essentially only consider the colored balls. As stated before, this can be done in $(2n)^n$ ways.

Feel free to comment on this post if further explanations are necessary; you made no indication in your post of what trouble you're having specifically with the problems.

$\endgroup$

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.