1
$\begingroup$

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.

  • 0
    @robjohn Hmm. May be I looked at the wrong time stamp (like the time o$f$ edit or something)? Doesn't matter much. Both contestants (if that's what it is about) can take a look at both, and be equally informed.2011-10-01

2 Answers 2

1

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

  • 0
    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 :-)2011-10-02
1

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

  • 0
    @robjohn I did not see the other question. Note that http://math.stackexchange.com/questions/69000/iterating-over-all-matrices-with-fixed-row-and-column-sums/69019#69019 is also essentially a dup (though somewhat disguised)2011-10-01