How to calculate the number of integer solution of a linear equation with constraints? If an equation is given like this ,
 $$x_1+x_2+...x_i+...x_n = S$$
and for each $x_i$ a constraint $$0\le x_i \le L_i$$
How do we calculate the number of Integer solutions to this problem?
 A: number of solutions of equation
$$x_1+x_2+...x_i+...x_n = S$$
and for each $x_i$ a constraint $$0\le x_i \le L_i=s-1,i=1,2,...,n$$
is
$$\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}\binom{n+S-si-1}{n-1}$$
formula for general case is more complicated.
A: Answer
The answer is the coefficient of $y^S$ in the polynomial $A(y)=\prod_{i=1}^{n}{(\sum_{j=0}^{L_i}{y^j})}$.
Reasoning
Define $f(S)$ to be the number of integer solutions to your problem that sum to $S$ and meet the other constraints. Then the ordinary generating function for $f(S)$ is: $$A(y)=\sum_{j=0}^{\infty}{f(j)y^j}$$
Define $g_i(S)$ to be the number of ways that just $x_i$ can sum to $S$. Then the ordinary generating function for each $g_i(S)$ is: $$A_i(y)=\sum_{j=0}^{\infty}{g_i(j)y^j}=\sum_{j=0}^{L_i}{y^j},i\in\{1,...,n\}$$
We can express $A(y)$ in terms of the $A_i(y)$:$$A(y)=\prod_{i=1}^{n}{A_i(y)}=\prod_{i=1}^{n}{(\sum_{j=0}^{L_i}{y^j})}$$
Example
$$x_1+x_2+x_3=S$$$$0\le x_1\le 4,0\le x_2\le 2,0\le x_3\le 1$$
$$A(y)=(1+y)(1+y+y^2)(1+y+y^2+y^3+y^4)$$$$=1+3x+5x^2+6x^3+6x^4+5x^5+3x^6+x^7$$
So there is $1$ integer solution when $S=0$ or $S=7$, there are $3$ integer solutions when $S=1$ or $S=6$, there are $5$ integer solutions when $S=2$ or $S=5$, and there are $6$ integer solutions when $S=3$ or $S=4$.
