# Integer solutions to $a_1+a_2+a_3+\cdots a_n = N$, where $l_i \leq a_i \leq r_i$ for each $i=1,2,\ldots,n$

Given $l_1, l_2, l_3, \ldots, l_n\in\mathbb{Z}$, $r_1, r_2, r_3, \ldots, r_n\in\mathbb{Z}$, and an integer $N$, find a general formula to calculate the number of ways that $N$ can be written as the sum $a_1 + a_2 + a_3 + \ldots+ a_n$, where $a_i$ is an integer such that $l_i \leq a_i \leq r_i$ for each $i=1,2,\ldots,n$.

I am newbie in combinatorics. I also know the stars and bars theorem. But I dont know how to solve this.
I can solve if only it is said $l_i \leq a_i$ But cant find a way to figure out how to handle $a_i \leq r_i$

• No answer yet :'( Jan 24 '17 at 20:36

Does this count as a formula you are searching for: $$\frac{1}{2\pi\text{i}}\,\oint_\gamma\,\frac{1}{z^{N+1}} \,\prod_{j=1}^n\,\left(\frac{z^{r_j+1}-z^{l_j}}{z-1}\right)\,\text{d}z\,?$$ Here, $\gamma$ is the positively oriented curve along the unit circle $\big\{z\in\mathbb{C}\,\big|\,|z|=1\big\}$.
Alternatively, we look at the generating function $$f(x):=\prod_{j=1}^n\,\frac{x^{l_j}-x^{r_j+1}}{1-x}=\frac{x^{l}}{(1-x)^n}\,\prod_{j=1}^n\,\left(1-x^{k_j}\right)=\frac{x^l}{(1-x)^n}\,\sum_{S\subseteq [n]}\,(-1)^{|S|}\,x^{\sum_{j\in S}\,k_j}\,\,,$$ where $[n]:=\{1,2,\ldots,n\}$, $l:=\sum_{j=1}^n\,l_j$, and $k_j:=r_j-l_j+1$ for $j=1,2,\ldots,n$. That is, $$f(x)=x^l\,\left(\sum_{m=0}^\infty\,\binom{n+m-1}{n-1}\,x^m\right)\,\left(\sum_{S\subseteq [n]}\,(-1)^{|S|}\,x^{\sum_{j\in S}\,k_j}\right)\,,$$ so $$f(x)=x^l\,\sum_{m=0}^\infty\,x^m\,\sum_{\substack{{S\subseteq[n]}\\{\sum_{j\in S}\,k_j\leq m}}}\,(-1)^{|S|}\,\binom{n+m-1-\sum_{j\in S}\,k_j}{n-1}\,.$$ The required answer will be the coefficient of $x^N$ in $f(x)$, for $N\geq \sum_{j=1}^n\,l_j$, and the answer is $$\small \sum_{\substack{{S\subseteq[n]}\\{\sum_{j\in S}\,k_j\leq N-l}}}\,(-1)^{|S|}\,\binom{n+N-l-1-\sum_{j\in S}\,k_j}{n-1}=\sum_{\substack{{S\subseteq[n]}\\{\sum_{j\in S}\,r_j\leq N-|S|}}}\,(-1)^{|S|}\,\binom{n+N-|S|-1-\sum_{j\in S}\,r_j}{n-1}\,.$$ An argument using the Principle of Inclusion and Exclusion should yield the same formula.
Reduce each range to $$0$$ to $$r_i - l_i$$ by defining $$u_i = a_i - l_i$$, then the sum to get is just $$N' = N - \sum_{1 \le i \le n} l_i$$. Then you have the problem to divide $$N'$$ stars into $$n$$ groups by $$n - 1$$ bars like "$$**||*|***$$" (here $$N'= 5, n = 4$$, the example solution is $$u_1 = 2, u_2 = 0, u_3 = 1, u_4 = 3$$). That is the same as the number of ways to string up $$N'$$ stars and $$n - 1$$ bars, which is just:
$$\binom{N' + n - 1}{n - 1} = \binom{N - \sum l_i + n - 1}{n - 1}$$
But this assumes no $$a_i$$ is limited, need to take the limits into account. This can be done by inclusion and exclusion: Compute how many solutions are with at least $$u_1 > r_1 - l_1$$, and so on. A veritable mess, true. Not hard, just messy.