Inclusion–exclusion principle

Find the number of soultion to this equation: $$x_1+x_2+x_3+x_4+x_5+x_6= 20$$ $$1 <= x_1, x_2, \ldots, x_6 \leq 4$$

I know that at the start we need to define:

$y_1=x_1-1$

$y_2=x_2-1$

$y_3=x_3-1$

$y_4=x_4-1$

$y_5=x_5-1$

$y_6=x_6-1$

So we end up with this:

$$y_1+y_2+y_3+y_4+y_5+y_5=14$$

and now I need to use the "Inclusion–exclusion principle" but how?

-
Did you mean to say that each $x_1, \ldots, x_6$ is an integer between 1 and 4 inclusive? –  Sasha Sep 28 '13 at 17:57
For the start, we want $y_i=x_i-1$. –  André Nicolas Sep 28 '13 at 17:58
@Sasha Yes that what I mean –  Gil Sep 28 '13 at 18:00
I would suggest $z_i = 4-x_i$ instead. –  Calvin Lin Sep 28 '13 at 18:02
@CalvinLin What is z? –  Gil Sep 28 '13 at 18:06
show 1 more comment

For each solution set $x_i$, we consider the change of variables $z_i = 4 - x_i$.

Then, the conditions become $z_1 + z_2 + z_3 + z_4 + z_5 + z_6 = 4$ and $0 \leq z_i \leq 3$.

Ignoring the upper bound on $z_i$, there are ${ 6+4 - 1 \choose 4 } =126$ solutions by the technique Stars and Bars.

There are 6 solutions where (at least) one of $z_i$ is strictly greater than 3. By the Inclusion and Exclusion principle, there are 120 solutions in total.

Of course, you could apply the technique PIE directly initially, but that is slightly tedious. Though that can be good practice too. Let $P_i$ be the sets of solutions where $x_i \geq 5$. Observe that at most 3 of them can be greater than or equal to 5.

Recall that the number of positive integer solutions by stars and bars to

$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = n$$

is ${n-1 \choose 5}$. Let's evaluate $|P_i|, |P_i \cap P_j|$ and $|P_i \cap P_j \cap P_k|$.

$P_1$ corresponds to solutions with $x_1 \geq 5$. using the change of variables $a_1 = 4 + x_1$, we thus have

$$a_1 + x_2 + x_3 + x_4+ x_5 + x_6 = 16.$$

There are ${ 15 \choose 5}$ solutions in this case.

Similarly, $|P_i \cap P_j| = {11 \choose 5}, |P_i \cap P_j \cap P_k | = {7 \choose 5}$.

Hence, by PIE,

$$|\cup P_i | = {6 \choose 1} {15 \choose 5} - { 6\choose 2} { 11 \choose 5} + {6 \choose 3} { 7 \choose 5} = 11508.$$

Hence, the number of solutions is ${19 \choose 5 } - 11508 = 120$ (Phew!)

-