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

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.

• Where did this sum come from? Commented May 21, 2022 at 23:04
• It might help to apply $\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}$ because then you can move $\binom{n}{r}$ outside the sum. Commented May 21, 2022 at 23:13
• @RobPratt It seems like your suggestion was instrumental to the solution I found. See my answer (in particular the start of the proof of Claim 3). Commented May 22, 2022 at 10:11

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

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

• This looks really nice. I assume the square bracket means you should select the indicated power of $z$ or $w$ for the expression. Is there any reference that talks about this notation? Commented May 22, 2022 at 19:23
• Thanks! This is the Egorychev method in formal power series. Commented May 22, 2022 at 19:31
• Brilliant! Thanks
– sku
Commented May 24, 2022 at 3:34

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.