Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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

share|improve this answer
    
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$? –  Nicholas Mar 31 at 13:06
1  
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. –  Nicholas R. Peterson Mar 31 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? –  Nicholas Mar 31 at 14:19
1  
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$? –  Nicholas R. Peterson Mar 31 at 14:37
1  
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$. –  Nicholas R. Peterson Mar 31 at 15:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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