Inclusion exclusion involving distribution.

79 Views Asked by At

This question was in my book in the inclusion-exclusion principle section. I really don't see how to apply it here. Any tips?

A candy maker distributes 3 types of coupons in the packages of Breakfast cereals, 1 in each package. How many different ways can a individual get at least one coupon of each type, buying only 6 breakfast cereal packs? Answer: 10

1

There are 1 best solutions below

2
On BEST ANSWER

You are asked for the cardinality of the set: $$\{(a_1,a_2,a_3)\in\mathbb Z_{\geq1}^3\mid a_1+a_2+a_3=6\}$$ which is the same as the cardinality of the set: $$\{(b_1,b_2,b_3)\in\mathbb Z_{\geq0}^3\mid b_1+b_2+b_3=3\}$$(to see this let $b_i:=a_i-1$)

This can be solved by means of stars and bars, giving as outcome:$$\binom{3+2}2=10$$

So in solving this the principle of inclusion/exclusion is not applied.

A (more complex) route that next to stars and bars also applies inclusion/exclusion is the following.

Let $X:=\{(a_1,a_2,a_3)\in\mathbb Z_{\geq0}^3\mid a_1+a_2+a_3=6\}$ and let $A_i$ be the subset of $X$ where $a_i=0$.

Then with insclusion exclusion we find:$$\left|A_{1}^{\complement}\cap A_{2}^{\complement}\cap A_{3}^{\complement}\right|=\left|X\right|-\left|A_{1}\cup A_{2}\cup A_{3}\right|=\left|X\right|-3\left|A_{1}\right|+3\left|A_{1}\cap A_{2}\right|=$$$$\binom{6+2}{2}-3\binom{6+1}{1}+3\binom{6+0}{0}=10$$

Maybe there is also a route purely based on inclusion/exclusion... I can't find it right now.