1
$\begingroup$

How many integer solutions exist for the following equation with the given constraint:

Equation: $t_1+t_2+\dots+t_n\le T$

Constraints: $0\le t_i\le s$, $i=1,\cdots,n$

Say for example, $T=1000, n=100, s=1$

I'd love to know a way to calculate this exactly or approximately. Thanks!

$\endgroup$
  • $\begingroup$ hint : you can use \le for $\le$ $\endgroup$ – mathreadler Oct 14 '18 at 13:57
2
$\begingroup$

HINT

One normally solves such problems with generating functions. For each of the $t_i$, the generating function is $$f_i(x) = 1 + x + \ldots + x^s = \frac{x^{s+1}-1}{x-1}$$ and since you have $n$ of them, the generating function for the entire problem is $$ f(x) = \prod_{k=1}^n f_i(x) = \left(\frac{x^{s+1}-1}{x-1}\right)^n $$ and so get the number of solutions of $\sum t_i = T$ you are looking for the coefficient of $x^T$ in $f(x)$, or $\left[x^T\right]f(x)$.

You want solutions for all $0 \le k \le T$ so the answer would be $$ \sum_{k=0}^t \left[x^k\right]f(x). $$ Can you finish this?

UPDATE

Note that $$ f(x) = \left(x^{s+1}-1\right)^n \cdot (x-1)^{-n}, $$ and each of the terms can be expanded by the Binomial Theorem, and the series multiplied to give the requested coefficient. You can use the classical Binomial Theorem for the first one, and the extended one for the second one, since $-n < 0$.

$\endgroup$
  • $\begingroup$ Thanks! I understand the logic, but I have difficult figuring out the explicit form of the coefficient, say in terms of some combinatorial number I guess? $\endgroup$ – G. Yu Oct 14 '18 at 21:30
  • $\begingroup$ @G.Yu please see the further update in the answer $\endgroup$ – gt6989b Oct 15 '18 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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