# Inclusion-exclusion principle: finding the number of solutions

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?

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*}

• That makes a lot of sense. Counting the solutions that don't follow the restrictions would be a lot easier, but I still don't see how I would do that. I see that the value of the intersections of $3$ and $4$ sets will be $0$, since it's impossible for $3$ or $4$ of the $x_i$'s to be greater than $7$. The value of the intersection of $2$ sets will be 1. But how do I calculate the values of a single $A_i$, and the value of $S$? – RBS Mar 31 '14 at 13:06
• There's a general formula here: the number of non-negative integer solutions to $x_1+\cdots+x_n=r$ is the same as the number of ways to put $r$ indistinguishable balls in to $n$ labeled boxes: $\binom{n+r-1}{r}$. (This comes from the classical "stars and bars" argument.) For the rest: counting solutions where $x_1$ is at least $8$ is the same as counting solutions to $y_1+8+x_2+x_3+x_4$, where $y_1$ is now any non-negative integer-valued variable. – Nick Peterson Mar 31 '14 at 14:15
• I was just looking up the stars and bars problem when you answered, so great timing on that! ;) However, I don't understand your last equation. What should the sum $y_1+8+x_2+x_3+x_4$ equal? – RBS Mar 31 '14 at 14:19
• Well, each $x_i$ has OGF $1+x+x^2+x^3+x^4+x^5+x^6+x^7$, since they can take any value between $0$ and $7$, inclusive; how do you combine those to get the OGF for $x_1+\cdots+x_4$? – Nick Peterson Mar 31 '14 at 14:37
• The $6\cdot1$ should be $6\cdot\binom{2+4-1}{2}=6\cdot10$; solutions with, say, $x_1,x_2\geq 8$ are equivalent to solutions to $y_1+y_2+x_3+x_4=2$ with $y_i,x_j\geq0$. – Nick Peterson Mar 31 '14 at 15:36