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?



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

  • $\begingroup$ 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$? $\endgroup$ – RBS Mar 31 '14 at 13:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Nick Peterson Mar 31 '14 at 14:15
  • $\begingroup$ 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? $\endgroup$ – RBS Mar 31 '14 at 14:19
  • 1
    $\begingroup$ 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$? $\endgroup$ – Nick Peterson Mar 31 '14 at 14:37
  • 1
    $\begingroup$ 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$. $\endgroup$ – Nick Peterson Mar 31 '14 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.