[Math] Use the inclusion-exclusion principle to determine

balls-in-binscombinatoricsinclusion-exclusion

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?

Best Answer

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

Related Question