# Inclusion-exclusion principle: Number of integer solutions to equations

The problem is:

Find the number of integer solutions to the equation $$x_1 + x_2 + x_3 + x_4 = 15$$ satisfying \begin{align} 2 \leq &x_1 \leq 4, \\ -2 \leq &x_2 \leq 1, \\ 0 \leq &x_3 \leq 6, \text{ and,} \\ 3 \leq &x_4 \leq 8 \>. \end{align}

I have read some papers on this question, but none of them explain clearly enough. I am especially confused when you must decrease the total amount of solutions to the equation—with no regard to the restrictions—from the solutions that we don't want. How do we find the intersection of the sets that we don't want? Either way, in helping me with this, please explain this step.

-
Using Generating Functions: math.stackexchange.com/questions/4643/… –  Aryabhata Apr 24 '11 at 15:50
@Moron: gfs work great but that's overkill at this stage. –  Mitch Apr 25 '11 at 16:07
@MItch: Hence a comment :-) –  Aryabhata Apr 25 '11 at 16:14
@Moron: Oh...I'm not thinking fast enough. –  Mitch Apr 25 '11 at 17:17

Let $y_1 = x_1-2$, $y_2 = x_2+2$, $y_3 = x_3$ and $y_4 = x_4-3$. Then you want to find the number of integer solutions to $y_1+y_2+y_3+y_4 = 12$ where $0 \leq y_1 \leq 2$, $0 \leq y_2 \leq 3$, $0 \leq y_3 \leq 6$ and $0 \leq y_4 \leq 5$. Let $A_1$ be the set of solutions such that $y_1 \geq 3$, $A_2$ be the set of solutions such that $y_2 \geq 4$, $A_3$ be the set of solutions such that $y_3 \geq 7$ and $A_4$ be the set of solutions such that $y_4 \geq 6$. Let $S$ be the total number of non-negative solutions with no restrictions. Then $|S|= \binom{15}{3}$. So you want to find $|S \ \backslash \ (A_1 \cup A_2 \cup A_3 \cup A_4)|$. So you use inclusion-exclusion to get $|A_1 \cup A_2 \cup A_3 \cup A_4|$.

-
Fixed. Thanks.. –  PEV Apr 24 '11 at 16:24
Something I dont understand. Where does |S|=C(18,3) come from? Also, my main problem is how to use the inclusion exclusion principle on |A1∪A2∪A3∪A4|. I'm somewhat of a noob... Thanks for the reply! Just a little bit more input and it will sink in. –  DAK Apr 24 '11 at 16:30
The numbers $C(n,3)$ are sometimes called tetrahedral numbers. Now, all the non-negative solutions of $y_1+y_2+y_3+y_4=12$ can be represented as point of a tetrahedron. I think however that it should be $C(15,3)$. –  Raskolnikov Apr 25 '11 at 13:00
I agree, I think it's $C(12 + 4 - 1, 3) = C(15,3)$. –  Ben Alpert Apr 25 '11 at 15:40

If you don't get the larger question, start smaller first.

• How many solutions to $x_1 + x_2 = 15$, no restrictions? (infinite of course)

• How many solutions where $0\le x_1$, $0\le x_2$?

• How many solutions where $6\le x_1$, $0\le x_2$?

• How many solutions where $6\le x_1$, $6\le x_2$? (these last questions don't really say anything about inclusion-exclusion yet)

• How many solutions where $0\le x_1\le 5$, $0\le x_2$? Hint: exclude the complement. This is the fist step of the exclusion.

• How many solutions where $0\le x_1\le 5$, $0\le x_2\le7$? Hint: exclude the both complements, but re-include where those two complements overlap (the intersection of those two excluded ranges - what is it), because you excluded the intersection twice.

That is the gist of it. Now it gets harder, because you need to do it for 4 variables not just 2. But that's the exercise, figuring out how to manage including/excluding/then including back of what you threw away too much of /then excluding back again that littlest bit messed up in that last step.

-

I'm not sure I can expand on PEV's hints in a comment, so I'll make it an answer.

You need to know the number of solutions of $$u_1+u_2+\dots+u_r=n$$ when the only restriction on the variables is that they be non-negative integers. Imagine $n+r-1$ dots in a line, and circle $r-1$ of them. The uncircled dots are $n$ in number, and the circled ones divide the uncircled ones into $r$ groups (some of which may be empty), so you get $r$ non-negative integers adding up to $n$. So the question becomes, how many ways can you choose which $r-1$ of the $n+r-1$ dots to circle? Unfortunately, PEV wrote 18-choose-3, where I think what's wanted is 15-choose-3, but now you should see how to get that part of the answer.

Then you ask how to use inclusion-exclusion. It isn't clear whether you mean that you don't see how to get a formula for the size of the union by using inc-excl, or whether you mean that you can write down a formula but don't see how to find the sizes of the $A_i$ and the various intersections that arise, so it's a little hard to help you here. I'll assume it's the second suggestion. So for PEV's $A_1$, let $v_1=y_1-3$, then you have $v_1+y_2+y_3+y_4=9$ and the variables are non-negative, so the previous paragraph applies. Similarly, for the intersection of $A_1$ and $A_2$, let $v_1=y_1-3$ and $v_2=y_2-4$, so you get $v_1+v_2+y_3+y_4=5$ with all variables non-negative.

Can you take it from there?

-
Thanks for the reply! My main concern is how to get the union for sets where we don't know their elements, so thats what your 'first suggestion'. So how does one find the intersection between A1 and A2, or any other pairs (or triples)? What formula should I use? Everything makes sense until that part. –  DAK Apr 25 '11 at 13:57
@DAK: Reread Gerry's last paragraph. For the intersection of $A_1$ and $A_2$, it's equivalent to solving $v_1+v_2+y_3+y_4=5$ with $v_1, v_2, y_3, y_4 \ge 0$. Just like the number of solutions to solve $y_1+y_2+y_3+y_4 = 12$ is $C(15,3)$, the number of solutions to that equation (and the size of the $\lvert A_1 \cap A_2 \rvert$ set) is $C(8,3)$. –  Ben Alpert Apr 25 '11 at 15:43
@DAK, you shouldn't use any formula, you should use thought. $A_1$ (in PEV's answer) is the solutions with $y_1\ge3$, $A_2$ is the solutions with $y_2\ge4$, so the intersection is the solutions with $y_1\ge3$ and $y_2\ge4$. Then deal with these as in the last sentence of my answer. I have a feeling I'm still missing just where it is you need help, so keep asking questions if it's still not clear. Or look at Mitch's answer, which nicely breaks it down into bite-size pieces. –  Gerry Myerson Apr 26 '11 at 4:26
Thank you everyone for your answers and comments. I managed to understand the problem. –  DAK Apr 27 '11 at 3:19