# How can we compute this quantity, constructed using motivation from Vandermonde's identity?

$$\sum_{k=0}^{r} {m \choose k}{n \choose r-k} = {m+n \choose r}$$

I wonder if we can use this formula or otherwise to calculate:

$$\sum_{k=0}^{r}k^l {m \choose k}{n \choose r-k}, l \in \mathbb{N} ?$$

or if not, at least when $$l=1,$$ namely:

$$\sum_{k=0}^{r}k {m \choose k}{n \choose r-k}?$$

I'd appreciate the relevant calculations or some links where I can find the above?

Let $$k_{(r)}$$ denote the falling factorial $$k(k-1)\cdots(k-r+1)$$. Recall that $$k^n=\sum_{r=1}^n {n\brace r}k_{(r)}$$, where $${n \brace r}$$ is a Stirling number of the second kind.

Expand $$k^l$$ into falling factorials, use the identity $$k_{(j)}\binom{m}k=m_{(j)}\binom{m-l}{k-l}$$, then apply Vandermonde's identity: \begin{align} \sum_kk^l\binom{m}k\binom{n}{r-k} &=\sum_k\sum_{j=1}^l{l \brace j} k_{(j)}\binom{m}k\binom{n}{r-k} \\&=\sum_{j=1}^l{l \brace j}\sum_k m_{(j)}\binom{m-j}{k-j}\binom{n}{r-k} \\&=\sum_{j=1}^l{l \brace j} m_{(j)}\binom{m+n-j}{r-j} \\&=\boxed{\binom{m+n}{r}\sum_{j=1}^l{l \brace j} \frac{\binom{m}j}{\binom{m+n}j}\cdot r_{(j)}} \end{align} I have replaced your summation with a another summation. However, this new summation only has $$l$$ terms. For example:

• $$l=1$$: $$\binom{m+n}r\cdot \left(1\cdot \frac{m}{m+n}\cdot r\right)$$

• $$l=2$$: $$\binom{m+n}r\cdot \left(1\cdot \frac{m}{m+n}\cdot r+1\cdot \frac{\binom{m}2}{\binom{m+n}2}\cdot r(r-1)\right)$$

• $$l=3$$: $$\binom{m+n}r\cdot \left(1\cdot \frac{m}{m+n}\cdot r+3\cdot \frac{\binom{m}2}{\binom{m+n}2}\cdot r(r-1)+1\cdot \frac{\binom{m}3}{\binom{m+n}3}\cdot r(r-1)(r-2)\right)$$

The $$l=1$$ equations represents the familiar fact that the the mean of the hypergeometric distribution is $$\frac{m}{m+n}\cdot r$$, and the other equations represent higher moments of the hypergeometric distribution.

• (+1). Verified. Commented Feb 1, 2021 at 20:57

We have for with the dominant parameter being $$p$$

$$\sum_{k=0}^r k^p {m\choose k} {n\choose r-k}$$

that it is

$$p! [w^p] \sum_{k=0}^r \exp(kw) {m\choose k} {n\choose r-k} \\ = p! [w^p] [z^r] (1+z)^n \sum_{k=0}^r \exp(kw) {m\choose k} z^k.$$

Now the coefficient extractor enforces the upper limit of the range and we may continue with

$$p! [w^p] [z^r] (1+z)^n \sum_{k\ge 0} \exp(kw) {m\choose k} z^k \\ = p! [w^p] [z^r] (1+z)^n (1+z\exp(w))^m \\ = p! [w^p] [z^r] (1+z)^n (1+z+z(\exp(w)-1))^m \\ = p! [w^p] [z^r] (1+z)^n \sum_{j=0}^m {m\choose j} (1+z)^{m-j} z^j (\exp(w)-1)^j \\ = [z^r] \sum_{j=0}^m {m\choose j} (1+z)^{m+n-j} z^j j! {p\brace j} \\ = \sum_{j=0}^m {m\choose j} {m+n-j\choose r-j} j! {p\brace j}.$$

Note that if $$m\gt p$$ the values with $$m\ge j\gt p$$ produce a zero Stirling number so we may lower $$m$$ to $$p.$$ If $$m\lt p$$ the values with $$p\ge j\gt m$$ produce a zero binomial coefficient and we may raise $$m$$ to $$p.$$ We thus obtain

$$\bbox[5px,border:2px solid #00A000]{ \sum_{j=0}^p {m\choose j} {m+n-j\choose m+n-r} j! {p\brace j}.}$$

a sum with $$p$$ non-zero terms except for $$p=0$$, when it has one term. (We could also use $$\min(m,p)$$ as the upper limit but we want to emphasize the dependence on $$p.$$) Note that in the initial sum for it to be non-zero with non-negative $$k$$ we must have $$m\ge k$$ and $$n\ge r-k$$ or $$k\ge r-n$$ so that $$m\ge k\ge r-n$$ and for the range not to be empty we must have $$m\ge r-n$$ or $$m+n-r\ge 0$$ which ensures that the middle binomial coefficient in the boxed form is non-zero and well defined. Observe that with $$p=0$$ we obtain $${m+n\choose m+n-r} = {m+n\choose r}$$ which is Vandermonde. A slight variation is

$$\bbox[5px,border:2px solid #00A000]{ \sum_{j=0}^p m^\underline{j} {m+n-j\choose m+n-r} {p\brace j}.}$$

Remark. This is the same as the formula that was first to appear.

We get

$${m+n\choose r} {p\brace j} {m\choose j} {m+n\choose j}^{-1} r^\underline{j} \\ = {p\brace j} {m\choose j} \frac{(m+n)!/(m+n-r)!/r!}{(m+n)!/(m+n-j)!/j!} r^\underline{j} \\ = {p\brace j} {m\choose j} j! {m+n-j\choose m+n-r} (r-j)! r^\underline{j} / r! = {p\brace j} {m\choose j} j! {m+n-j\choose m+n-r}.$$

Remark II. We may keep the $${m+n-j\choose r-j}$$ if we remember that it originates with $$[z^r] (1+z)^{m+n-j} z^j$$ and hence is zero when $$j\gt r.$$