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$

  • 1
    $\begingroup$ No answer yet :'( $\endgroup$ – 0123456789101112 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.


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.