Evaluating $\sum_{k=0}^{n}\binom{n}{k}\binom{k}{r}\binom{k}{s}(-1)^{k}$

Question

So far I've been able to determine that if $n, r, s$ are nonnegative integers, then $$ \sum_{k=0}^{n}\binom{n}{k}\binom{k}{r}\binom{k}{s}(-1)^{k} = \begin{cases} 0 &\qquad\text{ if } r+s < n, \\ \displaystyle (-1)^{n}\binom{n}{r} &\qquad\text{ if } r+s=n, \\ ?? &\qquad\text{ if } r+s>n. \end{cases} $$ I am wondering if there is a way to give a "closed form answer" for the sum in the case where $r+s>n$. WolframAlpha doesn't seems to give me anything sensible. Any ideas would be appreciated.

Perhaps I should say that this sum closely resembles a somewhat known identity given by $$ \sum_{k=0}^{n} \binom{n}{k}\binom{k}{r}x^{k} = x^{r}(1+x)^{n-r}\binom{n}{r}. $$ Plugging $x=1$ and $x=-1$ reduces this to some interesting looking identities involving binomial coefficients. However, the sum I'm trying to evaluate seems to be much harder to figure out.

Answer 1

Ok, I think I've found an answer along with a proof. I will go through a series of claims (of course there may be more efficient ways of going about this). The main result is in Claim 3.

Claim 1. For nonnegative integers $m, r, t$ we have $$ \sum_{j=0}^{m+t} \binom{m+t}{j}\binom{j+r}{t+r}(-1)^{j} = (-1)^{m+t}\binom{r}{m}. \tag*{$(1)$} $$

Proof. We proceed by Egorychev's method. We will use the fact that $$ \binom{j+r}{t+r} = \frac{1}{2\pi i}\oint \frac{(1+z)^{j+r}}{z^{t+r+1}} \, dz, $$ where the integral is a contour integral over a circle $|z|=\varepsilon$ for some $0<\varepsilon<\infty$. Using this fact, and interchanging the summation and integral signs when necessary, we have \begin{align*} \sum_{j=0}^{m+t} \binom{m+t}{j}\binom{j+r}{t+r}(-1)^{j} &= \sum_{j=0}^{m+t} \binom{m+t}{j} \left( \frac{1}{2\pi i}\oint \frac{(1+z)^{j+r}}{z^{t+r+1}} \, dz \right) (-1)^{j} \\[1.2ex] &= \frac{1}{2\pi i}\oint \; \sum_{j=0}^{m+t} \binom{m+t}{j} \frac{(1+z)^{j+r}}{z^{t+r+1}} (-1)^{j} \, dz \\[1.2ex] &= \frac{1}{2\pi i}\oint \frac{(1+z)^{r}}{z^{t+r+1}} \; \sum_{j=0}^{m+t} \binom{m+t}{j} (1+z)^{j} (-1)^{j} \, dz \\[1.2ex] &= \frac{1}{2\pi i}\oint \frac{(1+z)^{r}}{z^{t+r+1}} \; \sum_{j=0}^{m+t} \binom{m+t}{j} (-1-z)^{j} \, dz \\[1.2ex] &= \frac{1}{2\pi i}\oint \frac{(1+z)^{r}}{z^{t+r+1}} (1 - 1 - z)^{m+t} \, dz \\[1.2ex] &= \frac{1}{2\pi i}\oint \frac{(1+z)^{r}}{z^{t+r+1}} (-z)^{m+t} \, dz \\[1.2ex] &= \frac{1}{2\pi i}\oint \frac{(1+z)^{r}}{z^{r-m+1}} (-1)^{m+t} \, dz \\[1.2ex] &= (-1)^{m+t}\binom{r}{r-m} \\[1.2ex] &= (-1)^{m+t}\binom{r}{m}. \end{align*} $$\tag*{$\blacksquare$}$$

Claim 2. For nonnegative integers $n, r, s$ with $s\ge r$, we have $$ \sum_{k=0}^{n} \binom{n-r}{k-r}\binom{k}{s}(-1)^{k} = (-1)^{n}\binom{r}{n-s}. \tag*{$(2)$} $$

Proof. If $s > n$, then both sides of $(2)$ are clearly $0$, so for the proof let us assume $s\le n$. Take $m = n-s$ and $t = s-r$ and plug these into $(1)$. We obtain $$ \sum_{j=0}^{n-r} \binom{n-r}{j}\binom{j+r}{s}(-1)^{j} = (-1)^{n-r}\binom{r}{n-s}. $$ We can shift the summation index by taking $j = k-r$ (where $k$ is the new index). By doing this and then multiplying both sides by $(-1)^{r}$, we get $(2)$. $$\tag*{$\blacksquare$}$$

Claim 3. For nonnegative integers $n, r, s$, we have $$ \boxed{ \sum_{k=0}^{n}\binom{n}{k}\binom{k}{r}\binom{k}{s}(-1)^{k} = (-1)^{n}\binom{n}{n-r,\, n-s,\, r+s-n} } $$ where the RHS involves the multinomial coefficient.

Proof. Without loss of generality, assume $s\ge r$. Consider the fact that $$ \binom{n}{k}\binom{k}{r} = \binom{n}{r}\binom{n-r}{k-r} $$ and use this to obtain $$ \sum_{k=0}^{n}\binom{n}{k}\binom{k}{r}\binom{k}{s}(-1)^{k} = \binom{n}{r}\sum_{k=0}^{n} \binom{n-r}{k-r}\binom{k}{s}(-1)^{k}. $$ By Claim 2, we see that the RHS reduces to $$ \binom{n}{r}\cdot (-1)^{n}\binom{r}{n-s}. $$ This is then decomposed as \begin{align*} \binom{n}{r}\cdot (-1)^{n}\binom{r}{n-s} &= (-1)^{n} \frac{n!}{r!(n-r)!}\frac{r!}{(n-s)!(r-n+s)!} \\ &= (-1)^{n}\frac{n!}{(n-r)!(n-s)!(r+s-n)!}, \end{align*} and the fraction in the last expression can be identified as a multinomial coefficient, giving us $$ \sum_{k=0}^{n}\binom{n}{k}\binom{k}{r}\binom{k}{s}(-1)^{k} = (-1)^{n}\binom{n}{n-r,\, n-s,\, r+s-n} $$ as desired. $$\tag*{$\blacksquare$}$$

Answer 2

Suppose for $n,r,s \ge 0$ we seek a closed form of

$$\sum_{k=0}^{n} {n\choose k} (-1)^k {k\choose r} {k\choose s}.$$

We actually use $n\ge r$ and $n\ge s$ or else the two binomial coefficients in $k$ produce zero one or two times. We get

$$[z^r] [w^s] \sum_{k=0}^n {n\choose k} (-1)^k (1+z)^k (1+w)^k \\ = [z^r] [w^s] (1-(1+z)(1+w))^n = (-1)^n [z^r] [w^s] (z+w+zw)^n \\ = (-1)^n [z^r] [w^s] \sum_{k=0}^n {n\choose k} w^k (1+z)^k z^{n-k} \\ = (-1)^n [z^r] {n\choose s} (1+z)^s z^{n-s} = (-1)^n {n\choose s} {s\choose r+s-n} \\ = (-1)^n \frac{n!}{(n-s)! \times (r+s-n)! \times (n-r)!} \\ = (-1)^n {n\choose n-r, n-s, r+s-n}.$$

Answer 3

By reversing the order of summation and applying symmetry, you can rewrite your identity as $$\sum_{k=0}^n (-1)^k \binom{n}{k}\binom{n-k}{r}\binom{n-k}{s} = \binom{n}{n-r, n-s, r+s-n}.$$ Now let $R=n-r$ and $S=n-s$ to obtain $$\sum_{k=0}^n (-1)^k \binom{n}{k}\binom{n-k}{R-k}\binom{n-k}{S-k} = \binom{n}{R,S,n-(R+S)},$$ which you can prove combinatorially via inclusion-exclusion as follows. The RHS counts the number of ways to color $\{1,\dots,n\}$ with $R$ red, $S$ silver, and the remaining $n-(R+S)$ black (one color per element). The LHS is the inclusion-exclusion formula for the colorings with $R$ red and $S$ silver that avoid the $n$ properties that element $i$ is colored both red and silver.