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.

Possible Duplicate:
Number of combinations with repetitions (Constrained)

Given an equation of form $Z_1+Z_2+\cdots+Z_m = n$ , where each $X_i \leq Z_i \leq Y_i$ and $(0\leq X_i , Y_i \leq 100$), each Zi is an integer. Calculate no of possible solutions of given equation.Brute force method that one can think of is to put the values for each $Z_i$ in its respective range,no of solutions which satisfy the equations can be counted but it is very tedious.Is there any theorem or method of mathematics which can come to my rescue? Please give me some idea.

share|improve this question

marked as duplicate by robjohn, Quixotic, t.b., Mike Spivey, J. M. Oct 7 '11 at 12:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Are those bits integers? Reals? What? –  J. M. Oct 1 '11 at 12:01
    
They are integers. –  code_hacker Oct 1 '11 at 12:27
1  
Is this the same as this problem that I just answered? –  robjohn Oct 1 '11 at 13:03
    
How can we calculate the coefficient in that series? Is there any formula for this? –  code_hacker Oct 1 '11 at 13:14
1  
Funny, @robjohn. I just saw that migrated question, and voted to close that as an exact duplicate :-). It is probably an ongoing programming contest. If I read the timing data correctly this questions arrived a few minutes sooner? –  Jyrki Lahtonen Oct 1 '11 at 13:26

2 Answers 2

up vote 1 down vote accepted

The problem doesn't make sense unless the variables are integers, so I assume that.

I would iteratively (as a function of $m$) build a table containing numbers $S(j,k)$. Here $S(j,k)$ is the number of solutions of the system $$ Z_1+Z_2+\cdots+Z_j=k. $$

The initialization in the case $j=1$ is easy: $S(1,k)=1$, if $k$ is a possible value of $Z_1$, and $S(1,k)=0$ otherwise.

Assume that we have computed all the numbers $S(\ell,k)$ for some number of variables $\ell$. Then we have the recurrence relations for all $k$ $$ S(\ell+1,k)=\sum_{\text{$t$ is an allowed value for $Z_{\ell+1}$}}S(\ell,k-t). $$ That should do it. The number $S(m,n)$ is your answer.

Of course, you have to do a little bit of computation to decide on the lower and upper bounds of the indices in your table. It may or may not be easier, if you subtract $X_i$ from $Z_i$ so that the lower bound for the (partial) sums becomes zero. If you do that, you also have to subtract $\sum_i X_i$ from $n$.

share|improve this answer
    
I read your solution carefully and tried to implement it.Link to my implementation pastebin.com/mZN0PJ66 Can you please tell me if I'm doing it in the same way as you told or am I wrong? If I'm doing right is there anyway to improve it? Thanks in advance. –  code_hacker Oct 2 '11 at 6:40
    
@code_hacker: Can't you test your program? For example, if $X_i=0, Y_i=1$ for all $i$, then you should get the binomial coefficient ${m\choose n}$ as the answer. I think that robjohn's answer gives you more test cases. Also, the case $m=2$ you can surely do by hand, and check that your code gives the same answers. The point is that such testing is a way more reliable check than any cursory look I can perform :-) –  Jyrki Lahtonen Oct 2 '11 at 6:46
    
Thanks Jyrki Lahtonen for your help.I followed your advice and checked my implementation on several test cases.It worked fine on these test cases :-) –  code_hacker Oct 2 '11 at 7:07

A slightly less tedious method than brute force enumeration is to first convert your problem into one of the form $Z'_1+Z'_2+\cdots+Z'_m = n'$ , where each $0 \leq Z'_i \leq Y_i - X_i$, (here $Z'_i = Z_i-X_i$ and $n' = n - \sum_i X_i$. Now your count is the $n'$th degree term of $\prod_i(1+x+x^2+\cdots+x^{Y_i-X_i})$. (This is essentially equivalent to what Jyrki did.)

share|improve this answer
    
Correct. Alternative you can start counting possible values of $Z_1+Z_2+\cdots+Z_\ell$ from the minimum value $X_1+\cdots+X_\ell$ onwards. Probably your approach has more predictable memory requirements. –  Jyrki Lahtonen Oct 1 '11 at 16:53
    
This is essentially what I did in my answer to the other question. –  robjohn Oct 1 '11 at 17:06
    
@robjohn I did not see the other question. Note that math.stackexchange.com/questions/69000/… is also essentially a dup (though somewhat disguised) –  deinst Oct 1 '11 at 17:30

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