# Inclusion–exclusion principle

Find the number of solutions to this equation: $$x_1+x_2+x_3+x_4+x_5+x_6= 20$$ $$1\leq 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

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!)

Another possible way to solve this linear equation is to (by using the formula $x_1+x_2+\cdots+x_r=n\implies\dbinom{n+r-1}{r-1}$) We know that $x_i\geq1$ so we will subtract the minimum value from the equation assuming that all $x_i=x_i'+1$ and moving forward with that we get:$$x_1+x_2+\cdots+x_6=14$$ now we calculate the number of all integer solutions in this restriction (then we will move forward with the second one):$$\dbinom{14+6-1}{6-1}=\dbinom{19}{5}$$ and then we substitude values for $x_i$ as $4$ and subtract the situations because we use $\geq\square$ and subtract it from all the number of solutions in order to get $\leq\square$ moving on; $$x_1'+4+x_2+\cdots+x_6=14\implies 6\dbinom{10+6-1}{6-1}$$ (Because we repeat this for all $6$ variables) and then when two of them are $x_k'+4$ we say:$$x_1'+4+x_2'+4+x_3+\cdots+x_6=14\implies\dbinom{6}{2}\dbinom{6+6-1}{6-1}$$ For three variables: $$x_1'+x_2'+x_3'+12+\cdots+x_6=14\implies\dbinom{6}{3}\dbinom{2+6-1}{6-1}$$ This is where we stop because if we keep going with $4$ variables we end up in a situation where $x_k\leq0$ and we don't want that because we have established a position like $x_k\geq0$ after we subtracted the $1$s. So now we combine these situations with inclusion-exclusion principle, which basically makes us put $-$ and $+$ after another, but we start with $-$ because we are subtracting: $$\dbinom{19}{5}-6\dbinom{15}{5}+\dbinom{6}{2}\dbinom{11}{5}-\dbinom{6}{3}\dbinom{7}{5}=120$$