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

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.

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.

• Have you considered using generating functions? Like here, here or here. – rtybase Aug 16 '19 at 22:14
• @rtybase I can't really use it since i'm not there yet at my discrete math course :/ – Moria Aug 16 '19 at 22:16

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. ^_^
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.
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.