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

Question

This question already has answers here:

Counting bounded integer solutions to $\sum_ia_ix_i\leqq n$

(5 answers)

Closed 1 year ago.

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

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.