Given the equation $\begin{cases} x_1+x_2+x_3+x_4 =18\\ 0\leq x_i\leq 7 \text{ with } x_i \in \mathbb{N} \text{ and } 1\leq i\leq 4 \end{cases}$
how do I calculate the number of solutions with the inclusion-exclusion principle? (Given that $x_1=x_2=4, x_3=x_4=5$ and $x_1=x_2=5, x_3=x_4=4$ are two different solutions).
Furthermore, I'm also asked to calculate the number of solutions using a generating function.
How can I solve those two problems? Or could you give a hint?
Best Answer
Hint:
Let $S$ be the set of all non-negative integer solutions to $x_1+x_2+x_3+x_4=18$.
For $1\leq i\leq 4$, let $A_i$ be the set of all non-negative integer solutions to $x_1+\cdots+x_4=18$ in which $x_i\geq 8$. Then you want to find $\lvert \overline{A}_1\cap\cdots\cap\overline{A}_4\rvert$, the size of the complement (in $S$) of the $A_i$'s.
Inclusion-Exclusion tells us that $$ \begin{align*} \lvert\overline{A}_1\cap\cdots\cap\overline{A}_4\rvert&=\lvert S\rvert\\ &-(\lvert A_1\rvert+\lvert A_2\rvert+\lvert A_3\rvert+\lvert A_4\rvert)\\ &+(\lvert A_1\cap A_2\rvert+\lvert A_1\cap A_3\rvert+\lvert A_1\cap A_4\rvert+\lvert A_2\cap A_3\rvert+\lvert A_2\cap A_4\rvert+\lvert A_3\cap A_4\rvert)\\ &-(\lvert A_1\cap A_2\cap A_3\rvert+\lvert A_1\cap A_2\cap A_4\rvert+\lvert A_1\cap A_3\cap A_4\rvert+\lvert A_2\cap A_3\cap A_4\rvert)\\ &+\lvert A_1\cap A_2\cap A_3\cap A_4\rvert. \end{align*} $$