5
$\begingroup$

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?

  • 2
    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](http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle) to take into account the caps $A,B$, and $C$.2012-07-02

3 Answers 3

10

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.

4

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.

  • 1
    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!)2012-07-02
0

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.