1
$\begingroup$

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$

$\endgroup$
1
  • 1
    $\begingroup$ No answer yet :'( $\endgroup$ Jan 24 '17 at 20:36
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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} $$

This is the stars and bars argument.

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.

$\endgroup$

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.