3
$\begingroup$

Use the inclusion-exclusion principle to determine :

(a) the number of ways there are to choose nineteen balls (identical apart from their colour) from a pile of red, blue, yellow and green balls if there have to be at most seven balls of each colour?

(b) the number of arrangements of length 9 of the numbers 1, 2, 3 and 4 (repetitions allowed) in which each number occurs at least once.

I have no idea how to approach part (a). For part (b), I think that the sets, say Ai, should be set up to be arrangements that do not have 1 or 2 or 3 or 4. Example : A1 be the set of length 9 of the numbers 2,3,4 and A2 be the set of length 9 of the numbers 1,3,4 and so on. Would this be correct and, if it is, how would I proceed with it?

$\endgroup$
6
$\begingroup$

For (a), there are $\binom{19+4-1}{4-1}$ ways to choose without restrictions. If one of the $\binom41$ restrictions is violated, that leaves $\binom{19+4-1-8}{4-1}$ possibilities (since $8$ balls of the colour for which the restriction is violated are fixed), and if one of the $\binom42$ pairs of restrictions are violated, that leaves $\binom{19+4-1-8-8}{4-1}$ possibilities. Three or four restrictions can't be violated simultaneously. Thus inclusion-exclusion yields

$$ \binom{22}3-\binom41\binom{14}3+\binom42\binom63=204\;. $$

For a general treatment, see Balls In Bins [here: Colours] With Limited Capacity.

For (b), your approach is right. There are $n^9$ arrangements using at most $n$ digits, so inclusion-exclusion using the sets you defined yields

$$ 4^9-\binom41\cdot3^9+\binom42\cdot2^9-\binom43\cdot1^9=186480\;. $$

$\endgroup$
3
$\begingroup$

$a)$

How many ways are there to select them so that two colors have more than $7$ balls? There are $\binom{4}{2}=6$ ways to choose the two colors. After that we can go ahead and take out $8$ balls of each of those colors. We must now select $19-16=3$ balls out of $4$ colors. By stars and bars there are $\binom{6}{3}=20$ ways to do this. So $6\cdot20=120$ ways in total.

How many ways are there to select them so that exactly one color has more than $7$ balls? First select the color in $4$ ways,let us assume it is red. After this take out $8$ balls of that color. We must now select $19-8=11$ balls out of $4$ colors, by stars and bars there are $\binom{14}{3}=364$ ways to do so. However out of those $364$ ways there are $20$ ways in which red and blue appear more than seven times, $20$ ways in which red and green appear more than $7$ times and $20$ ways in which red and yellow appear more than $7$ times. Therefore there are $364-3\cdot20=304$ ways in which only red is repeated. Therefore there are $4\cdot304=1216$ colorings in which exactly one color appears more than seven times.

Once we have this we can count the number of colorings in which no color apears more than $7$ times. This is because if we are allowed to color freely then by stars and bars there are $\binom{22}{3}=1540$ colorings. Therefore there are $1540-120-1216=204$ coloring in which no color appears more than $7$ times.

$b)$

This one is easier, we solve for an arbitrary length $n$ of words, where $n\geq 4$:

There are $1+1+1+1$ sequences with exactly one number.

How many sequences have exactly $2$ numbers? there are $6$ ways to choose the numbers and then $2^{n}-2$ sequences, so $6(2^n-2)$ total.

How many sequences have exactly $3$ numbers? There are $4$ ways to choose them. After this there are $3^n$ sequences with those $3$ numbers, out of these $3$ use exactly $1$ number and $3(2^n-2)$ use exactly $2$ numbers. Hence $3^n-3\cdot2^n-3$ use all of those three numbers. So $4(3^n-3\cdot2^n+3)$ total.

Therefore there are $4^n-4-6(2^n-2)-4(3^n-3\cdot2^n+3)$ words that use all four numbers.

$\endgroup$
2
$\begingroup$

We outline a solution of (a).

We are not allowed to use more than $7$ blue balls, or more than $7$ yellow balls, and so on. Let us forget temporarily about that restriction.

If there is no restriction, then the problem is standard Stars and Bars. We want to find the number of solutions of $x_1+x_2+x_3+x_4=19$ in non-negative integers. I will assume you know how to handle that. Call this number $A$.

From the number $A$ obtained above, we must subtract the nuber of bad choices, where we have more than $7$ of some colour(s).

How many bad choices are there where we have more than $7$ red? Grab $8$ red. Now we must choose $11$ balls, with colours chosen from our four colours. The number of ways to do this can be computed using Stars and Bars. Call this number $B$. There are also $B$ ways to have more than $7$ yellow, and so on.

So is the number of bad choices equal to $4B$? Not quite. For it is possible to have, for example, more than $7$ red and more than $7$ yellow. How many ways cn we have more than $7$ of each of these colours? Grab $8$ red and $8$ yellow. Now we must choose $3$ more balls. It is easy to count how many ways there are to do this. Call this number $C$. Similarly, there are $C$ ways to have more than $7$ red and more than $7$ blue, and so on, for a total of $\binom{4}{2}C$.

These $6C$ choices have been double-counted in the sum $B+B+B+B$. So the number of bad choices is $4B-6C$.

It follows that the number of ways to do the job is $A-4B+6C$.

$\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.