Inclusion-exclusion principle: Number of integer solutions to equations

Solution 1:

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|$.

Solution 2:

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.

Solution 3:

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?