# Count the number of solutions of the inequality $x + y + z \leq N$

Problem Given $A, B, C$ and $N$. How many integer solutions are there of the following inequality: $$x + y + z \leq N$$ where $0 \leq x \leq A, 0 \leq y \leq B, 0 \leq z \leq C$?

When $A + B + C \leq N$, the solution is obvious $(A + 1) \cdot (B + 1) \cdot (C + 1)$
The general formula for the number of solutions of the form $x + y + z = N$, for $x, y , z \geq 0$ is $\dbinom{N + r -1}{r - 1}$. Unfortunately, I couldn't find a way to bring this idea into place. Any suggestion?

-
First, add a fourth variable $w\ge 0$ and count solutions to $w+x+y+z=N$ subject to the conditions $0\le w,0\le x\le A$, and so on. Then use inclusion-exclusion to take into account the caps $A,B$, and $C$. – Brian M. Scott Jul 2 '12 at 1:30

The main trick is to add a fourth variable to take up the slack between $x+y+z$ and $N$. You know that there are $\binom{N+3}3$ solutions to $w+x+y+z=N$ in non-negative integers, so there are also $\binom{N+3}3$ solutions to $x+y+z\le N$ in non-negative integers. Now we have to throw out the solutions that exceed one of the caps $A,B$, and $C$.

Counting non-negative solutions to $w+x+y+z=N$ in which $x>A$ is the same as counting non-negative solutions to $w+x+y+z=N-A-1$, of which there are $$\binom{N-A-1+3}3=\binom{N-A+2}3\;.$$ Similarly, there are $\binom{N-B+2}3$ non-negative solutions to $w+x+y+z=N$ in which $y>B$ and $\binom{N-C+2}3$ in which $z>C$. Thus, a better approximation to the desired number is

$$\binom{N+3}3-\binom{N-A+2}3-\binom{N-B+2}3-\binom{N-C+2}3\;.\tag{1}$$

However, it’s possible that a non-negative solution to $w+x+y+z=N$ exceeds two caps, and $(1)$ overcorrects for those unwanted solutions by subtracting each of them twice. The same reasoning used to calculate the correction terms above shows that there are $$\binom{N-A-B+1}3$$ solutions exceeding the $A$ and $B$ caps, $$\binom{N-A-C+1}3$$ exceeding the $A$ and $C$ caps, and $$\binom{N-B-C+1}3$$ exceeding the $B$ and $C$ caps. Thus, we must add to the expression in $(1)$ the sum

$$\binom{N-A-B+1}3+\binom{N-A-C+1}3+\binom{N-B-C+1}3\;.\tag{2}$$

Finally, we have to subtract the number of solutions that exceed all three caps, which is $$\binom{N-A-B-C}3\;.\tag{3}$$

The final count is $(1)+(2)-(3)$, where the parenthesized numbers refer to the numbered expression above.

-
Very nice explanation. Thanks! – Chan Jul 2 '12 at 1:55

It's the coefficient of $t^N$ in $$(1+t+t^2+\cdots+t^A)(1+t+t^2+\cdots+t^B)(1+t+t^2+\cdots+t^C)(1+t+t^2+\cdots)$$

All the terms are geometric series. Use the formula to sum them, then use the Binomial Theorem to expand. For details, see any good Discrete Math text.

-
Most of the standard introductory discrete math texts that I’ve seen in the U.S. $-$ and I was the main person teaching it for many years at my university $-$ don’t discuss generating functions at all. One of the few exceptions is Grimaldi’s Discrete and Combinatorial Mathematics, which is at a noticeably higher level, albeit still introductory. (I’m not knocking the solution, mind you!) – Brian M. Scott Jul 2 '12 at 1:52

Let $r=N-(x+y+z)$ gives a new equation $x+y+z+r=N$ where $0\leq x\leq A,0\leq y\leq B,0\leq z\leq C$ and $r \geq 0$. Now you can find number of solutions = coefficient of $t^N$ in $$(1+t+t^2+\cdots+t^A)(1+t+t^2+\cdots+t^B)(1+t+t^2+\cdots+t^C)(1+t+t^2+\cdots)$$.These are geometric series and have simple formula.then you can expand using binomial theorem and find corresponding coefficient. If the upper bound on any variable like $x,y,z,$ or $r$ is greater than $N$, then you can take the series corresponding to that variable infinite(without bound). This is useful as infinite geometric series sum is ${(1-t)}^{-1}$ and it's easy to find coefficients from its binomial expansion.

-