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

Question

Vadermonde's identity states that

$$ \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?

Answer 1

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.

Answer 2

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