Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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 to take into account the caps $A,B$, and $C$. –  Brian M. Scott Jul 2 '12 at 1:30
add comment

3 Answers

up vote 9 down vote accepted

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.

share|improve this answer
    
Very nice explanation. Thanks! –  Chan Jul 2 '12 at 1:55
add comment

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.

share|improve this answer
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!) –  Brian M. Scott Jul 2 '12 at 1:52
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.