Number of solutions to the equation $x_1+x_2+x_3+x_4=19$ with $0\leq x_i\leq 8$

Question

Find the number of solutions to the equation $x_1+x_2+x_3+x_4=19$ with $0\leq x_i\leq 8$.

I know that I should use inclusion-exclusion, but I don't quite see why.

If I had this problem:

Find the number of solutions to the equation $x_1+x_2+...+x_5=10$ with no restrictions to $x_i$:

The solution to this would be $14 \choose 10$ (like a stars-bars problem).

Back to the first problem, I see why can't use that... Let's say I want to solve something equivalent such as:

$(x_1+8)+(x_2+8)+(x_3+8)+(x_4+8)=19$ with no restrictions to $x_i$.

That would be $x_1+x_2+x_3+x_4=-13$ which doesn't make sense as I'm working with natural numbers.

Can someone explain me why inclusion-exclusion applies to this? I understand the theorem but I don't get why I should use it on this.

Answer 1

The stars and bars strategy is a good start, but it leaves you with solutions you don't want like $19+0+0+0=19$. So then you use I/E to subtract out solutions where $x_1>8$, which is just like $(y_i+8)+x_2+y_2+z_2=19$, but of course there are more cases than that, and then you have to add back in solutions where two variables are greater than eight yadda yadda yadda. ^_^

Answer 2

Hint: Let $A_i$ be a set of all $(x_1,x_2,x_3,x_4)$ such that $x_i\geq 9$. Then use a PIE.

Answer 3

One can apply a generating function approach $$ \begin{align} \left[x^{19}\right]\left(1+x+\dots+x^8\right)^4 &=\left[x^{19}\right]\left(\frac{1-x^9}{1-x}\right)^4\\ &=\left[x^{19}\right]\left(1-x^9\right)^4\sum_{k=0}^\infty(-1)^k\binom{-4}{k}x^k\\ &=\left[x^{19}\right]\left(1-4x^9+6x^{18}-4x^{27}+x^{36}\right)\sum_{k=0}^\infty\binom{k+3}{3}x^k\\ &=\binom{22}{3}-4\binom{13}{3}+6\binom{4}{3}\\[9pt] &=420 \end{align} $$ Note that the last two lines are same as in an answer using stars-and-bars and inclusion-exclusion.