Sum of binomial coefficients involving $n,p,q,r$

Question

Sum of binomial product $\displaystyle \sum^{n}_{r=0}\binom{p}{r}\binom{q}{r}\binom{n+r}{p+q}$

Simplifying $\displaystyle \frac{p!}{r!\cdot (p-r)!} \cdot \frac{q!}{r!\cdot (q-r)!}\cdot \frac{(n+r)!}{(p+q)! \cdot (n+r-p-q)!}$.

Could some help me with this, thanks

Answer 1

It is convenient to use the coefficient of operator $[t^r]$ to denote the coefficient of $t^r$ in a series. This way we can write e.g. \begin{align*} \binom{p}{r}=[t^r](1+t)^p \end{align*}

The following is valid \begin{align*} \color{blue}{\sum_{r=0}^n\binom{p}{r}\binom{q}{r}\binom{n+r}{p+q}=\binom{n}{p}\binom{n}{q}} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{r=0}^n}&\color{blue}{\binom{p}{r}\binom{q}{r}\binom{n+r}{p+q}}\\ &=\sum_{r=0}^n\binom{p}{r}\binom{q}{q-r}\binom{n+r}{p+q}\\ &=\sum_{r=0}^\infty[t^r](1+t)^p[v^{q-r}](1+v)^q[w^{p+q}](1+w)^{n+r}\tag{1}\\ &=[v^q](1+v)^q[w^{p+q}](1+w)^n\sum_{r=0}^\infty(v(1+w))^r[t^r](1+t)^p\tag{2}\\ &=[v^q](1+v)^q[w^{p+q}](1+w)^n(1+v(1+w))^p\tag{3}\\ &=[v^q](1+v)^{p+q}[w^{p+q}](1+w)^n\left(1+\frac{vw}{1+v}\right)^p\tag{4}\\ &=[v^q](1+v)^{p+q}[w^{p+q}]\sum_{k=0}^{p+q}\binom{n}{k}w^k\sum_{j=0}^p\binom{p}{j}\left(\frac{v}{1+v}\right)^jw^j\tag{5}\\ &=[v^q](1+v)^{p+q}\sum_{k=0}^{p+q}\binom{n}{k}[w^{p+q-k}]\sum_{j=0}^p\binom{p}{j}\left(\frac{v}{1+v}\right)^jw^j\\ &=[v^q](1+v)^{p+q}\sum_{k=0}^{p+q}\binom{n}{k}\binom{p}{p+q-k}\frac{v^{p+q-k}}{(1+v)^{p+q-k}}\tag{6}\\ &=\sum_{k=p}^{p+q}\binom{n}{k}\binom{p}{k-q}[v^{k-p}](1+v)^k\tag{7}\\ &=\sum_{k=p}^{p+q}\binom{n}{k}\binom{p}{k-q}\binom{k}{p}\\ &=\binom{n}{p}\sum_{k=p}^{p+q}\binom{p}{k-q}\binom{n-p}{k-p}\tag{8}\\ &=\binom{n}{p}\sum_{k=0}^{q}\binom{p}{k+p-q}\binom{n-p}{k}\tag{9}\\ &=\binom{n}{p}\sum_{k=0}^{q}\binom{p}{q-k}\binom{n-p}{k}\tag{10}\\ &\color{blue}{=\binom{n}{p}\binom{n}{q}} \end{align*} and the claim follows.

Comment:

• In (1) we apply the coefficient of operator for each binomial coefficient.

• In (2) we use the linearity of the coefficient of operator and apply the rule $[t^{p}]t^qA(t)=[t^{p-q}]A(t)$.

• In (3) we apply the substitution rule of the coefficient of operator with $t:=v(1+w)$ \begin{align*} A(z)=\sum_{r=0}^\infty a_rz^r=\sum_{r=0}^\infty z^r[t^r]A(t) \end{align*}

• In (4) we factor out $(1+v)^p$.

• In (5) we apply the binomial summation formula twice. Since we want to select the coefficient of $w^{p+q}$ we can restrict the upper limit of the left sum with $k=p+q$.

• In (6) we select the coefficient of $w^{p+q-k}$.

• In (7) we do some simplifications and can restrict the lower limit of the sum with $k=p$.

• In (8) we apply the cross product $\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$.

• In (9) we shift the summation index and start from $k=0$.

• In (10) we apply the Chu-Vandermonde identity.

Answer 2

This is Bizley’s identity (6.42 in Gould's book "Combinatorial identities"): $$\sum^{n}_{r=0}\binom{p}{r}\binom{q}{r}\binom{n+r}{p+q}=\binom{n}{p}\binom{n}{q}.$$ A nice combinatorial proof can be found in the following paper by Székely as a special case of a more general identity (see Corollary 3):

Common origin of cubic binomial identities. A generalization of Surányi's proof on Le Jen Shoo's formula

Answer 3

Here is a derivation based upon generalised hypergeometric functions. We obtain using rising factorials $(a)_{k}:=a(a+1)\cdots(a+k-1)$ \begin{align*} \color{blue}{\sum_{r=0}^n}&\underbrace{\color{blue}{\binom{p}{r}\binom{q}{r}\binom{n+r}{p+q}}}_{=: t_r}=\sum_{r=0}^{n}t_r=t_0\sum_{r=0}^n\prod_{j=0}^{r-1}\frac{t_{j+1}}{t_j}\\ &=\binom{n}{p+q}\sum_{r=0}^n\prod_{j=0}^{r-1}\binom{p}{j+1}\binom{q}{j+1}\binom{n+j+1}{p+q}\\ &\qquad\qquad\qquad\cdot\binom{p}{j}^{-1}\binom{q}{j}^{-1}\binom{n+j}{p+q}^{-1}\\ &=\binom{n}{p+q}\sum_{r=0}^n\prod_{j=0}^{r-1} \frac{\left(n+j+1\right)\left(p-j\right)\left(q-j\right)}{\left(j+1\right)^2\left(n-p-q+j+1\right)}\\ &=\binom{n}{p+q}\sum_{r=0}^n\frac{(n+1)_r(-p)_r(-q)_r}{(1)_r^2(n-p-q+1)_r}\\ &=\binom{n}{p+q}{_3F_2}\left(n+1,-p,-q;1,n-p-q+1;1\right)\tag{1}\\ &=\binom{n}{p+q}\frac{(-n)_q(1+p)_q}{(1)_q(-n+p)_q}\tag{2}\\ &=\binom{n}{p+q}\frac{(-1)^qn!}{(n-q)!}\,\frac{(p+q)!}{p!}\,\frac{1}{q!}\,\frac{(-1)^q(n-p-q)!}{(n-p)!}\\ &=\frac{n!}{p!(n-p)!}\,\frac{n!}{q!(n-q)!}\\ &\,\,\color{blue}{=\binom{n}{p}\binom{n}{q}} \end{align*} and the claim follows.

In (1) we write the sum as $_3F_2$ generalized hypergeometric function. This function has the nice property that the sum of the denominator parameters is one more than the sum of the numerator parameters. It is evaluated at $z=1$ and one of the numerator parameters is a negative integer. Such a series is called balanced and it obeys the Pfaff-Saalschütz identity \begin{align*} {_3F_2}\left(-n,a,b;c,1+a+b-c-n;1\right)=\frac{(c-a)_n(c-b)_n}{(c)_n(c-a-b)_n} \end{align*} which is used in (2).

Answer 4

The proposed identity can be derived (putting $r=s$) from this more general one $$ \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( \matrix{ m - \left( {r - s} \right) \cr k \cr} \right)\left( \matrix{ n + \left( {r - s} \right) \cr n - k \cr} \right)\left( \matrix{ r + k \cr m + n \cr} \right)} = \left( \matrix{ r \cr m \cr} \right)\left( \matrix{ s \cr n \cr} \right)\quad \quad \left| \matrix{ \,{\rm 0} \le {\rm integer \, }m,n \hfill \cr \;{\rm real}\;r,s \hfill \cr} \right. $$ reported in "Concrete Mathematics" - pag. 171, and which is demonstrated through the following passages: $$ \begin{gathered} \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} m - \left( {r - s} \right) \\ k \\ \end{gathered} \right)\left( \begin{gathered} n + \left( {r - s} \right) \\ n - k \\ \end{gathered} \right)\left( \begin{gathered} r + k \\ m + n \\ \end{gathered} \right)} = \hfill \\ = \sum\limits_{\begin{subarray}{l} \left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right) \\ \left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,n} \right) \end{subarray}} {\left( \begin{gathered} m - \left( {r - s} \right) \\ k \\ \end{gathered} \right)\left( \begin{gathered} n + \left( {r - s} \right) \\ n - k \\ \end{gathered} \right)\left( \begin{gathered} r \\ m + n - j \\ \end{gathered} \right)\left( \begin{gathered} k \\ j \\ \end{gathered} \right)} = \hfill \\ = \sum\limits_{\begin{subarray}{l} \left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right) \\ \left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,m + n} \right) \end{subarray}} {\left( \begin{gathered} m - \left( {r - s} \right) \\ k \\ \end{gathered} \right)\left( \begin{gathered} k \\ j \\ \end{gathered} \right)\left( \begin{gathered} n + \left( {r - s} \right) \\ n - k \\ \end{gathered} \right)\left( \begin{gathered} r \\ m + n - j \\ \end{gathered} \right)} = \hfill \\ = \sum\limits_{\begin{subarray}{l} \left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right) \\ \left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,m + n} \right) \end{subarray}} {\left( \begin{gathered} m - \left( {r - s} \right) \\ j \\ \end{gathered} \right)\left( \begin{gathered} m - \left( {r - s} \right) - j \\ k - j \\ \end{gathered} \right)\left( \begin{gathered} n + \left( {r - s} \right) \\ n - k \\ \end{gathered} \right)\left( \begin{gathered} r \\ m + n - j \\ \end{gathered} \right)} = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,m + n} \right)} {\left( \begin{gathered} m - \left( {r - s} \right) \\ j \\ \end{gathered} \right)\left( \begin{gathered} m + n - j \\ n - j \\ \end{gathered} \right)\left( \begin{gathered} r \\ m + n - j \\ \end{gathered} \right)} = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,m + n} \right)} {\left( \begin{gathered} m - \left( {r - s} \right) \\ j \\ \end{gathered} \right)\left( \begin{gathered} m + n - j \\ m \\ \end{gathered} \right)\left( \begin{gathered} r \\ m + n - j \\ \end{gathered} \right)} = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,m + n} \right)} {\left( \begin{gathered} m - \left( {r - s} \right) \\ j \\ \end{gathered} \right)\left( \begin{gathered} r \\ m \\ \end{gathered} \right)\left( \begin{gathered} r - m \\ n - j \\ \end{gathered} \right)} = \hfill \\ = \left( \begin{gathered} r \\ m \\ \end{gathered} \right)\left( \begin{gathered} s \\ n \\ \end{gathered} \right) \hfill \\ \end{gathered} $$ consisting in:

• Vandermonde de-convolution
• shift of the 4th binomial
• "trinomial revision"
• sum on $k$ by Vandermonde convolution
• symmetry
• "trinomial revision"
• sum on $j$ by Vandermonde convolution