# $A = x + y + z$, number of solutions in $Z$ if $x, y, z$ are bounded in intervals

For the equation $x + y = A$, it's easy, when you notice that when iterating over all possible $x$, the number of solutions for $y$ is $0$ at the beginning, then increases by $1$, then stays constant, then decreases by $1$, and at the end $0$. This can be calculated in $O(1)$.

$l_1 < a < u_1$, $l_2 < b < u_2$, $l_3 < c < u_3$. I'm looking for a general answer for all $u_i$, $l_i$, $A$ ($i = 1, 2, 3$).

I assume this problem is just as easy, but it's hard to find the formula, since i have to think in $3$ dimensions instead of $2$.

example: $2 < x < 5$, $1 < y < 5$, $3 < z < 7$, $A = 11$, the answer is 5.

-
In the 2d case, a formula can be obtained by Pick's Theorem. However there is direct analogue for Pick's Theorem in 3d. This is not a proof, but it provides evidence, that a simple closed formula for the 3d version does not exists. – A.Schulz Jan 11 '13 at 14:18
@A.Schulz Principle of Inclusion and Exclusion should work, and it's not that bad. (Oh, I just realized OP said that in the comments) – Calvin Lin Jan 11 '13 at 15:25

The number of non-negative integer solutions to $x+y+z=11$ where $2<x<5, 1<y<5, 3<z<7$ is equal to the number of integer solutions to $a+b+c=2$ where $0\leq a\leq 1$, $0\leq b\leq 2$, $0\leq c\leq 2$ by setting $a=x-3$, $b=y-2$, $c=z-4$.
In this case it is easy to count the number of solutions: $\binom{2+3-1}{3-1}-1=\binom{4}{2}-1=5$, since there is only one 'bad' option: $a=2,b=0,c=0$.
I was asking about any general case $l_1 < a < u_1$, $l_2 < b < u_2$, $l_3 < c < u_3$, and any $A$. This one turned easy bedause the 'bad' options are easy to count by hand. – Bojan Serafimov Jan 11 '13 at 13:54
I just realised $C_A =${$x_1, x_2, x_3$ | $x_i \in A$ iff $x_i < u_i$ for $i = 1, 2, 3$} So the result is $|C_{\{\emptyset\}}| - |C_{\{1\}}| - |C_{\{2\}}| - |C_{\{3\}}| + |C_{\{1, 2\}}| + |C_{\{2, 3\}}| + |C_{\{1, 3\}}| - |C_{\{1, 2, 3\}}|$ – Bojan Serafimov Jan 11 '13 at 14:29