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.

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.

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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
1  
That's what I meant. I wrote this example to show how one should approach the general case. –  Dennis Gulko Jan 12 '13 at 8:51

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.