3
$\begingroup$

For some fixed positive integers $r_1,\ldots,r_n$, I would like to find a sum:

$$ \sum_{i_1+\cdots+i_n=k}\binom{r_1+i_1}{r_1}\cdots\binom{r_n+i_n}{r_n}=\sum_{i_1+\cdots+i_n=k}\binom{r_1+i_1}{i_1}\cdots\binom{r_n+i_n}{i_n}, $$

where $k=0,\ldots,r_1+\cdots+r_n$ ($i_j$ ranges from $0$ to $r_j$, for $j=1,\ldots,n$).

If reformulate the problem. Multiply $n$ finite sums:

$$ \sum_{i_1=0}^{r_1}\binom{r_1+i_1}{r_1}\cdots\sum_{i_n=0}^{r_n}\binom{r_n+i_n}{r_n} $$

collect and sum parts such that $i_1+\cdots+i_n=k$. What is the result of every such sum.

I have found similar question here, but I can not connect it to this problem. Also found a paper which uses probabilistic method to establish several generalisations of Vandermonde identity (which to my dilettante view is somewhat similar to my problem).

Here is a small example just to be clear what I want to achieve. Let $n=3$ and $r_1=1$, $r_2=2$, $r_3=3$. Now take $k=3$, it takes six combinations of $(i_1,i_2,i_3)$: $(1,1,1)$, $(1,2,0)$, $(1,0,2)$, $(0,1,2)$, $(0,2,1)$, $(0,0,3)$ so that $i_1+i_2+i_3=k$ (note that $i_1, i_2, i_3$ can take values at most $1$, $2$ and $3$ respectively). So the sum is:

\begin{align*} &&{2\choose1}{3\choose2}{4\choose3}+{2\choose1}{4\choose2}{3\choose3}+{2\choose1}{2\choose2}{5\choose3}+\\ &&{1\choose1}{3\choose2}{5\choose3}+{1\choose1}{4\choose2}{4\choose3}+{1\choose1}{2\choose2}{6\choose3}=\\ &&24+12+20+30+24+20=130. \end{align*}

$\endgroup$
7
  • $\begingroup$ you put "$i_j$ ranges from $0$ to $r_j$" : is that an actual requirement ? $\endgroup$
    – G Cab
    Jul 7 '20 at 19:22
  • $\begingroup$ $k=0$ when all $i_j=0$ and $k=r_1+\cdots+r_n$ when $i_1=r_1,\ldots,i_n=r_n$. For some fixed value of $k$, take all possible combinations of $i_1,\ldots,i_n$ so that they sum up to $k$. $\endgroup$ Jul 8 '20 at 5:53
  • $\begingroup$ In your example you forgot the following combinations: $(2,0,1),(2,1,0),(3,0,0),(0,3,0)$. Taking them into account the result will be $165$. $\endgroup$
    – user
    Jul 8 '20 at 11:21
  • 1
    $\begingroup$ @user Please note, that $i_1,\ldots,i_n$ can take values at most $r_1,\ldots,r_n$ respectively. $\endgroup$ Jul 8 '20 at 11:58
  • $\begingroup$ Sorry. I have overlooked this additional requirement. $\endgroup$
    – user
    Jul 8 '20 at 12:38
1
$\begingroup$

Here is what can be obtained with generating function technique:

${r+i \choose r}=[x^i]\frac{1}{(1-x)^{r+1}}$, where $[x^i]f(x)$ is the coefficient of $x^i$ in the power series expansion of $f(x)$. Then $$ \sum_{i_1+\cdots+i_n=k}\binom{r_1+i_1}{r_1}\cdots\binom{r_n+i_n}{r_n}=[x^k]\frac{1}{(1-x)^{r_1+\cdots+r_n+n}}={r_1+\cdots+r_n+n-1+k \choose k} $$

$\endgroup$
3
  • 1
    $\begingroup$ That does not hold when I take an example. For $r_1=1$, $r_2=2$, $r_3=3$ and $k=3$ it takes six combinations of $(i_1,i_2,i_3)$: $(1,1,1)$, $(1,2,0)$, $(1,0,2)$, $(0,1,2)$, $(0,2,1)$, $(0,0,3)$. And the sum is $24+12+20+30+24+20=130$. $\endgroup$ Jul 8 '20 at 6:23
  • $\begingroup$ @user Please note, that $i_1,\ldots,i_n$ can take values at most $r_1,\ldots,r_n$ respectively. This example shows that the result is not Binomial coefficient. $\endgroup$ Jul 8 '20 at 11:36
  • 1
    $\begingroup$ Ok then my answer is wrong, and it seems to me that the question is much more difficult given these restrictions on the $i_j$. May be investigating the case $n=2$ would give insights or new ideas. $\endgroup$
    – René Gy
    Jul 8 '20 at 18:37
0
+100
$\begingroup$

So if I properly understood your question, you are looking for $$ S({\bf r}_{\,n} ,m) = \sum\limits_{\left\{ {\matrix{ {0\, \le \,k_{\,j} \, \le \,r_{\,j} } \cr {\,k_{\,1} + k_{\,2} + \cdots + k_{\,n} \, = \,m} \cr } } \right.} {\left( \matrix{ r_{\,1} + k_{\,1} \cr k_{\,1} \cr} \right) \left( \matrix{ r_{\,2} + k_{\,2} \cr k_{\,2} \cr} \right) \cdots \left( \matrix{ r_{\,n} + k_{\,n} \cr k_{\,n} \cr} \right)} $$ where we can consider ${\bf r}_{\,n}$ as a vector in $n$ dimensions.

If it was not for the limitation $0\, \le \,k_{\,j} \, \le \,r_{\,j} $ the above would be a convolution of the $n$ binomials, giving an ogf which is the product of $1/(1-x)^{r_{\,j}+1 }$ as per Renè answer.

With the excursion of $k_{\,j} $ limited to $[0, \,r_{\,j}]$ we have instead a truncated version of the above which we can express as follows. $$ \eqalign{ & F(x,r_{\,j} ) = \sum\limits_{0\, \le \,k\, \le \,r_{\,j} } {\left( \matrix{ r_{\,j} + k \cr k \cr} \right)x^{\,k} } = \sum\limits_{0\, \le \,k\, \le \,r_{\,j} } {\left( \matrix{ r_{\,j} + k \cr r_{\,j} \cr} \right)x^{\,k} } = \cr & = \sum\limits_{0\, \le \,k\,} {\left( \matrix{ r_{\,j} + k \cr r_{\,j} \cr} \right)x^{\,k} } - x^{\,r_{\,j} + 1} \sum\limits_{\,0\, \le \,k\,} {\left( \matrix{ 2r_{\,j} + 1 + k \cr r_{\,j} \cr} \right)x^{\,k} } \cr} $$

Indicating with $t_{\,k}$ the coefficient in the second sum $$ t_{\,k} = \left( \matrix{ 2r_{\,j} + 1 + k \cr r_{\,j} \cr} \right) = {{\left( {2r_{\,j} + 1 + k} \right)^{\,\underline {\,r_{\,j} \;} } } \over {r_{\,j} !}} = {{\left( {r_{\,j} + 2 + k} \right)^{\,\overline {\,r_{\,j} \,} } } \over {1^{\,\overline {\,r_{\,j} \,} } }} $$ we have $$ \eqalign{ & t_{\,0} = \left( \matrix{ 2r_{\,j} + 1 \cr r_{\,j} \cr} \right) \cr & {{t_{\,k + 1} } \over {t_{\,k} }} = {{\left( {r_{\,j} + 3 + k} \right)^{\,\overline {\,r_{\,j} \,} } } \over {\left( {r_{\,j} + 2 + k} \right)^{\,\overline {\,r_{\,j} \,} } }} = {{\left( {2r_{\,j} + 2 + k} \right)} \over {\left( {r_{\,j} + 2 + k} \right)}} \cr} $$ so one way to express a single term would be through the hypergeometric function $$ \eqalign{ & F(x,r_{\,j} ) = \sum\limits_{0\, \le \,k\, \le \,r_{\,j} } {\left( \matrix{ r_{\,j} + k \cr k \cr} \right)x^{\,k} } = \sum\limits_{0\, \le \,k\, \le \,r_{\,j} } {\left( \matrix{ r_{\,j} + k \cr r_{\,j} \cr} \right)x^{\,k} } = \cr & = \sum\limits_{0\, \le \,k\,} {\left( \matrix{ r_{\,j} + k \cr k \cr} \right)x^{\,k} } - x^{\,r_{\,j} + 1} \sum\limits_{\,0\, \le \,k\,} {\left( \matrix{ 2r_{\,j} + 1 + k \cr r_{\,j} \cr} \right)x^{\,k} } = \cr & = {1 \over {\left( {1 - x} \right)^{\,r_{\,j} + 1} }} - x^{\,r_{\,j} + 1} \left( \matrix{ 2r_{\,j} + 1 \cr r_{\,j} \cr} \right) {}_2F_{\,1} \left( {\left. {\matrix{ {2r_{\,j} + 2,\;1} \cr {r_{\,j} + 2} \cr } \;} \right|\;x} \right) \cr} $$

But now, multiplying the terms $$ G(x,{\bf r}_{\,n} ) = \sum\limits_{0\, \le \,m} {S({\bf r}_{\,n} ,m)x^{\,m} } = \prod\limits_{j = 1}^n {F(x,r_{\,j} )} $$ leads to a complicated expression.

Conclusion: lacking a "compact" form to express the truncated binomial, tere is not much to do to
render similarly "compact" your sum.

$\endgroup$
1
  • $\begingroup$ thanks indeed for the bounty, and thanks twice since I had to give, alas, a .. negative answer $\endgroup$
    – G Cab
    Jul 18 '20 at 13:41

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.