# number of integer solutions for $t_1 + t_2 + \dots +t_n\le T$ with constrains for each variable $0\le t_i\le s$

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!

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

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