Principle of inclusion and exclusion

Question

How many integer solutions can we have for the equation $x_1 + x_2 + x_3 = 18$, if $0 \leq x_1 \leq 6$, $4 \leq x_2 \leq 9$ and $7 \leq x_3 \leq 14$?

Using the Principle of inclusion and Exclusion: I have found

$S_0$ = $\binom{9}{7} $

However, I am stuck as to how to go about calculating $S_1$, $S_2$ and $S_3$. I believe that there is no solution for $S_2$ and $S_3$.

Answer 1

This is the stars and bars problem. You can set up an equivalent question. Subtract out $4$ from both sides so that $0 \leq x_{2} \leq 5$. Similarly, subtract out $7$ so $0 \leq x_{3} \leq 7$. This leaves us with $x_{1} + x_{2} + x_{3} = 7$.

We can use a generating function to give us our inclusion-exclusion formula. Note that for $x_{1}$, we have the generating function: $f(x) = 1 + x + x^{2} + ... + x^{6} = \frac{1 - x^{7}}{1 - x}$.

Similarly, for $x_{2}, x_{3}$, we have the functions $g(x) = \sum_{i=0}^{5} x^{i} = \frac{1 - x^{6}}{1 - x}$ and $h(x) = \sum_{i=0}^{7} x^{i} = \frac{1 - x^{8}}{1 - x}$.

By rule of product, we multiply $f, g, h$ and are interested in the coefficient of $x^{7}$.

So our product is: $$k(x) = \frac{1 - x^{5} - x^{6} - x^{7} + x^{11} + x^{12} + x^{13} - x^{18}}{(1 - x)^{3}}$$

Now $\frac{1}{(1-x)^{3}} = \sum_{i=0}^{\infty} \binom{i + 3 - 1}{i} x^{i}$

And so we multiply the expansion of the denominator by the numerator, keeping only the terms where we have $x^{7}$:

$$\binom{7 + 3 - 1}{7} - \binom{2 + 3 - 1}{2} - \binom{1 + 3 - 1}{1} - 1$$

And this gives you your inclusion-exclusion formula very methodically.

Answer 2

Using $y_1=x_1, y_2=x_2-4, y_3=x_3-7$, we get

$y_1+y_2+y_3=7$ where $0\le y_1\le6, \;\;0\le y_2\le5, \;\;0\le y_3\le 7$.

If we let S be the set of solutions in nonnegative integers,

$A_1$ be the set of solutions with $y_1\ge7$, and $A_2$ the set of solutions with $y_2\ge6$,

then $|S|-|A_1|-|A_2|+|A_1\cap A_2|=\dbinom{9}{2}-1-3+0=32.$

Answer 3

I follow the approach here, which is the answer by user84413, which I explain in more detail.

As seen before, using $y_1=x_1$, $y_2=x_2-4$, $y_3=x_3-7$ we may equivalently consider $y_1+y_2+y_3=7$ subject to $0\le y_1\le 6$, $0\le y_2\le 5$ and $0\le y_3\le 7$. Hence, we want to know the number of elements in $\mathcal S=(\mathcal T_{7,1,7}\cup\mathcal T_{7,2,6}\cup\mathcal T_{7,3,8})^{\mathrm c}\subseteq\mathcal T_7$, where $\mathcal T_s=\{y\in\mathbb Z_{\ge 0}^3:\sum_{i=1}^3y_i=s\}$ and $\mathcal T_{s,i,u}=\{y\in\mathcal T_s:y_i\ge u\}$. This way to define $\mathcal S$ using de Morgan's law allows to use the Inclusion-Exclusion Principle. To be precise, let $\mathcal S_1=\mathcal T_{7,1,7}$, $\mathcal S_2=\mathcal T_{7,2,6}$ and $\mathcal S_3=\mathcal T_{7,3,8}$. Then we have $$|\mathcal S|=|\mathcal T_7|-\sum_{k=1}^{3}(-1)^{k+1}\sum_{1\le i_1<\cdots<i_k\le 3}\left|\bigcap_{j=1}^{k}\mathcal S_{i_j}\right|.$$ Notice that $|\mathcal T_s|=\binom{s+3-1}{s}=\binom{s+2}{s}$ using starts and bars. Further, notice that $$\mathcal T_{s,1,u}=\left\{y\in\mathbb Z_{\ge 0}^3:\sum_iy_i=s,y_1\ge u\right\} =\{(z_1+u,z_2,z_3):z\in\mathcal T_{s-u}\},$$ which yields $|\mathcal T_{s,i,u}|=|\mathcal T_{s-u}|$ since we chose $i=1$ only for brevity. Analogously, we get $|\mathcal T_{s,i,u}\cap\mathcal T_{s,j,v}|=|\mathcal T_{s-u-v}|$ for $i\neq j$ and $|\mathcal T_{s,1,u}\cap\mathcal T_{s,2,v}\cap\mathcal T_{s,3,w}|=|\mathcal T_{s-u-v-w}|$. Notice that $\mathcal T_{s}=0$ for $s<0$ and hence $\mathcal S=\binom{7+2}{7}-\binom{0+2}{0}-\binom{1+2}{1}=\binom{9}{2}-1-3=32$.