Simplifying $ {m\choose l}^{-1}\sum_ii^p{n\choose i}{m-n\choose l-i} $

Question

I am trying to simplify the following expression:

$$ {m\choose l}^{-1}\sum_ii^p{n\choose i}{m-n\choose l-i} $$

where the sum is over all allowed $i$ values, i.e. $\max(0,l-m+n)\le i\le l$ and all variables are non-negative integers. I know that the expression has a value of 1 for $p=0$ from the Chu–Vandermonde identity, but I am wondering if I can simplify the sum away for $p=1$ and $p=2$. Thank you!

Answer 1

For $p=1$ we have

$$\sum_ii\binom{n}i\binom{m-n}{\ell-i}=n\sum_i\binom{n-1}{i-1}\binom{m-n}{\ell-i}=n\binom{m-1}{\ell-1}\;.$$

With a bit more work we can use the ame idea to dispose of the case $p=2$:

$$\begin{align*} \sum_ii^2\binom{n}i\binom{m-n}{\ell-i}&=n\sum_ii\binom{n-1}{i-1}\binom{m-n}{\ell-i}\\ &=n\sum_i(i-1)\binom{n-1}{i-1}\binom{m-n}{\ell-i}+\\ &\quad\quad+n\sum_i\binom{n-1}{i-1}\binom{m-n}{\ell-i}\\ &=n(n-1)\sum_i\binom{n-2}{i-2}\binom{m-n}{\ell-i}+n\binom{m-1}{\ell-1}\\ &=n(n-1)\binom{m-2}{\ell-2}+n\binom{m-1}{\ell-1}\;. \end{align*}$$

Answer 2

In seeking to simplify

$$\sum_{q=0}^l q^p {n\choose q} {m-n\choose l-q}$$

we use

$$q^p = \sum_{r=1}^p {q\choose r} {p\brace r} r!,$$

(distribute $q$ different possible values into $p$ slots and classify according to the number $r$ of different values that are present). We thus obtain

$$\sum_{q=0}^l \sum_{r=1}^p {q\choose r} {p\brace r} r! {n\choose q} {m-n\choose l-q} \\ = \sum_{r=1}^p {p\brace r} r! \sum_{q=0}^l {q\choose r} {n\choose q} {m-n\choose l-q}.$$

Now we have as in the first answer

$${n\choose q} {q\choose r} = \frac{n!}{(n-q)! \times r! \times (q-r)!} = {n\choose r} {n-r\choose n-q}$$

so that we obtain

$$\sum_{r=1}^p {p\brace r} r! {n\choose r} \sum_{q=0}^l {n-r\choose n-q} {m-n\choose l-q} \\ = \sum_{r=1}^p {p\brace r} r! {n\choose r} [z^{l}] (1+z)^{m-n} \sum_{q=0}^l {n-r\choose n-q} z^q.$$

Here the coefficient extractor enforces the range and we find for the term covered by the extractor

$$[z^{l}] (1+z)^{m-n} \sum_{q\ge 0} {n-r\choose n-q} z^q = [z^{l}] (1+z)^{m-n} \sum_{q=0}^n {n-r\choose n-q} z^q \\ = [z^l] (1+z)^{m-n} z^n \sum_{q=0}^n {n-r\choose q} z^{-q} = [z^l] (1+z)^{m-n} z^n \left(1+\frac{1}{z}\right)^{n-r}.$$

Returning to the full sum we find

$$\sum_{r=1}^p {p\brace r} r! {n\choose r} [z^l] (1+z)^{m-n} z^r (1+z)^{n-r}.$$

We thus get the closed form involving $p$ terms:

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

or alternatively

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

This gives for $p=2:$

$${2\brace 1} n {m-1\choose l-1} + {2\brace 2} n (n-1) {m-2\choose l-2} \\ = n {m-1\choose l-1} + n (n-1) {m-2\choose l-2}.$$

confirming the result from the first answer. We get for $p=3$

$${3\brace 1} n {m-1\choose l-1} + {3\brace 2} n (n-1) {m-2\choose l-2} + {3\brace 3} n (n-1) (n-2) {m-3\choose l-3} \\ = n {m-1\choose l-1} + 3 n (n-1) {m-2\choose l-2} + n (n-1) (n-2) {m-3\choose l-3}.$$