# Combinatorial proof that $\sum \limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$ when $n$ is even

In my answer here I prove, using generating functions, a statement equivalent to $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$$ when $n$ is even. (Clearly the sum is $0$ when $n$ is odd.) The nice expression on the right-hand side indicates that there should be a pretty combinatorial proof of this statement. The proof should start by associating objects with even parity and objects with odd parity counted by the left-hand side. The number of leftover (unassociated) objects should have even parity and should "obviously" be $2^n \binom{n}{n/2}$. I'm having trouble finding such a proof, though. So, my question is

Can someone produce a combinatorial proof that, for even $n$, $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}?$$

Some thoughts so far:

Combinatorial proofs for $\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n$ are given by Phira here and by Brian M. Scott here. The proofs are basically equivalent. In Phira's argument, both sides count the number of paths of length $2n$ starting from $(0,0)$ using steps of $(1,1)$ and $(1,-1)$. By conditioning on the largest value of $2k$ for which a particular path returns to the horizontal axis at $(2k,0)$ and using the facts that there are $\binom{2k}{k}$ paths from $(0,0)$ to $(2k,0)$ and $\binom{2n-2k}{n-k}$ paths of length $2n-2k$ that start at the horizontal axis but never return to the axis we obtain the left-hand side.

With these interpretations of the central binomial coefficients $2^n \binom{n}{n/2}$ could count (1) paths that do not return to the horizontal axis by the path's halfway point of $(n,0)$, or (2) paths that touch the point $(n,0)$. But I haven't been able to construct the association that makes these the leftover paths (nor do all of these paths have even parity anyway). So perhaps there's some other interpretation of $2^n \binom{n}{n/2}$ as the number of leftover paths.

Update. Some more thoughts:

There's another way to view the identity $\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n$. Both sides count the number of lattice paths of length $n$ when north, south, east, and west steps are allowed. The right side is obvious. The left side has a similar interpretation as before: $\binom{2k}{k}$ counts the number of NSEW lattice paths of length $k$ that end on the line $y=0$, and $\binom{2n-2k}{n-k}$ counts the number of NSEW lattice paths of length $n-k$ that never return to the line $y =0$. So far, this isn't much different as before. However, $2^n \binom{n}{n/2}$ has an intriguing interpretation: It counts the number of NSEW lattice paths that end on the diagonal $y = x$ (or, equivalently, $y = -x$). So maybe there's an involution that leaves these as the leftover paths. (Proofs of all of these claims can be found on this blog post, for those who are interested.)

-
I have set a bounty for this problem. After trying for some time, I feel that "new" (to me :-)) techniques might be necessary to handle the cancelations among the terms. I am especially interested in an inclusion-exclusion based proof, which I believe should exist. –  Srivatsan Dec 6 '11 at 7:35
I was thinking of a more "literal" interpretation of the RHS. I was thinking of the number of paths from (0,0) to (n/2,n/2) whereby each step is colored in one of two colors. The part I find difficult to think about is the LHS. Since each path has n edges and thus n colors, we can represent the coloring with 2n characters, which connects the LHS to the RHS (as the top binomial coefficients add to 2n in the LHS) but I fail to see how to continue. –  picakhu Dec 7 '11 at 15:45
Here's one tantalizing bit of cancellation: Start with Phira's interpretation (the LHS counts walks which return to $0$ for the last time at time $2k$). Fix any odd $t$, and consider all walks which return to $0$ for the first time at $2t$. The sum over all such walks is $0$, since after conditioning on the first $2t$ steps we're effectively left with the same sum over walks of length $2(n-t)$ and $n-t$ is odd. So the left hand side can be thought of as counting walks which never return to $0$ at a time in $\{2,6,10,14,\dots, 2n-2\}$. (continued in next comment) –  Kevin Costello Dec 8 '11 at 8:46
Conversely, as noted in the original post, the right hand side can be thought of as walks which never return to $0$ at a time in $\{2,4,6,8,\dots, n\}$. Similar in form, but I still don't see a direct bijection between them. –  Kevin Costello Dec 8 '11 at 8:48
The bounty I have set for this question has expired. However to encourage further progress on this problem, I hereby announce an unofficial “lifelong” bounty of +300 reps. (Once an answer is posted, I will start the bounty to reward it.) Note however that the bounty will be cancelled immediately if the OP takes the question over to MO. –  Srivatsan Dec 14 '11 at 9:53

Divide by $4^n$ so that the identity reads (again, for $n$ even)

$$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n} (-1)^k = \frac{1}{2^n} \binom{n}{n/2}. \tag{1}$$

Claim 1: Select a permutation $\sigma$ of $[n]$ uniformly at random. For each cycle $w$ of $\sigma$, color $w$ red with probability $1/2$; otherwise, color it blue. This creates a colored permutation $\sigma_C$. Then $$\binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n}$$ is the probability that exactly $k$ of the $n$ elements of a randomly-chosen permutation $\sigma$ are colored red. (See proof of Claim 1 below.)

Claim 2: Select a permutation $\sigma$ of $[n]$ uniformly at random. Then, if $n$ is even, $$\frac{1}{2^n} \binom{n}{n/2}$$ is the probability that $\sigma$ contains only cycles of even length. (See proof of Claim 2 below.)

Combinatorial proof of $(1)$, given Claims 1 and 2: For any colored permutation $\sigma_C$, find the smallest element of $[n]$ contained in an odd-length cycle $w$ of $\sigma_C$. Let $f(\sigma_C)$ be the colored permutation for which the color of $w$ is flipped. Then $f(f(\sigma_C)) = \sigma_C$, and $\sigma_C$ and $f(\sigma_C)$ have different parities for the number of red elements but the same probability of occurring. Thus $f$ is a sign-reversing involution on the colored permutations for which $f$ is defined. The only colored permutations $\sigma_C$ for which $f$ is not defined are those that have only even-length cycles. However, any permutation with an odd number of red elements must have at least one odd-length cycle, so the only colored permutations for which $f$ is not defined have an even number of red elements. Thus the left-hand side of $(1)$ must equal the probability of choosing a colored permutation that contains only even-length cycles. The probability of selecting one of the several colored variants of a given uncolored permutation $\sigma$, though, is that of choosing an uncolored permutation uniformly at random and obtaining $\sigma$, so the left-hand side of $(1)$ must equal the probability of selecting a permutation of $[n]$ uniformly at random and obtaining one containing only cycles of even length. Therefore, $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n} (-1)^k = \frac{1}{2^n} \binom{n}{n/2}.$$

(Clearly, $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n} = 1,$$ which gives another combinatorial proof of the unsigned version of $(1)$ mentioned in the question.)

Proof of Claim 1: There are $\binom{n}{k}$ ways to choose which $k$ elements of a given permutation will be red and which $n-k$ elements will be blue. Given $k$ particular elements of $[n]$, the number of ways those $k$ elements can be expressed as the product of $i$ disjoint cycles is $\left[ {k \atop i} \right]$, an unsigned Stirling number of the first kind. Thus the probability of choosing a permutation $\sigma$ that has those $k$ elements as the product of $i$ disjoint cycles and the remaining $n-k$ elements as the product of $j$ disjoint cycles is $\left[ {k \atop i} \right] \left[ {n-k \atop j}\right] /n!$, and the probability that the $i$ cycles are colored red and the $j$ cycles are colored blue as well is $\left[ {k \atop i} \right] \left[ {n-k \atop j}\right]/(2^i 2^j n!).$ Summing up, the probability that exactly $k$ of the $n$ elements in a randomly chosen permutation are colored red is \begin{align} \frac{\binom{n}{k}}{n!} \sum_{i=1}^k \sum_{j=1}^{n-k} \frac{\left[ {k \atop i} \right] \left[ n-k \atop j \right]}{2^i 2^j} = \frac{\binom{n}{k}}{n!} \sum_{i=1}^k \frac{\left[ {k \atop i} \right]}{2^i} \sum_{j=1}^{n-k} \frac{\left[ {n-k \atop j} \right]}{2^j}. \end{align} The two sums are basically the same, so we'll just do the first one. $$\sum_{i=1}^k \frac{\left[ {k \atop i} \right]}{2^i} = \left( \frac{1}{2} \right)^{\overline{k}} = \prod_{i=0}^{k-1} \left(\frac{1}{2} + i\right) = \frac{1 (3) (5) \cdots (2k-1)}{2^k} = \frac{1 (2) (3) \cdots (2k-1)(2k)}{2^k 2^k k!} = \frac{(2k)!}{4^k k!}.$$ (The first equality is the well-known property that Stirling numbers of the first kind are used to convert rising factorial powers to ordinary powers. This property can be proved combinatorially. For example, Vol. 1 of Richard Stanley's Enumerative Combinatorics, 2nd ed., pp. 34-35 contains two such combinatorial proofs.)

Thus the probability that exactly $k$ of the $n$ elements of a randomly chosen permutation are colored red is $$\frac{\binom{n}{k}}{n!} \frac{(2k)!}{4^k k! } \frac{(2n-2k)!}{4^{n-k} (n-k)!} = \binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n}.$$

Proof of Claim 2: Since there can be no odd cycles, $\sigma(1) \neq 1$. Thus there are $n-1$ choices for $\sigma(1)$. We have already chosen the element that maps to $\sigma(1)$, but otherwise there are no restrictions on the value of $\sigma(\sigma(1))$, and so we have $n-1$ choices for $\sigma(\sigma(1))$ as well.

Now $n-2$ elements are unassigned. If $\sigma(\sigma(1)) \neq 1$, then we have an open cycle. We can't assign $\sigma^3(1) = 1$, as that would close the current cycle at an odd number of elements. Also, $\sigma(1)$ and $\sigma^2(1)$ are already taken. Thus there are $n-3$ choices for the value of $\sigma^3(1)$. If $\sigma(\sigma(1)) = 1$, then we have just closed an even cycle. Selecting any unassigned element in $[n]$, say $j$, we cannot have $\sigma(j) = j$, as that would create an odd cycle, and $1$ and $\sigma(1)$ are already taken. Thus we have $n-3$ choices for $\sigma(j)$ as well.

In general, if there are $i$ elements unassigned and $i$ is even, there is either one even-length open cycle or no open cycles. If there is an open cycle, we cannot close it, and so we have $i-1$ choices for the next element in the cycle. If there is not an open cycle, we select the smallest unassigned element $j$. Since we cannot have $\sigma(j) = j$, there are $i-1$ choices for $\sigma(j)$. Either way, we have $i-1$ choices. If there are $i$ elements unassigned and $i$ is odd, though, there must always be an odd-length open cycle. Since we can close it, there are $i$ choices for the next element in the cycle.

All together, then, if $n$ is even then the number of permutations of $[n]$ that contain only cycles of even length is $$(n-1)^2 (n-3)^2 \cdots (1)^2 = \left(\frac{n!}{2^{n/2} (n/2)!}\right)^2 = \frac{n!}{2^n} \binom{n}{n/2}.$$ Thus the probability of choosing a permutation uniformly at random and obtaining one that contains only cycles of even length is $$\frac{1}{2^n} \binom{n}{n/2}.$$

(I've been thinking about this problem off and on for the two months since I first posted it. What finally broke it open for me was discovering the interpretation of the unsigned version of the identity mentioned as #60 on Richard Stanley's "Bijective Proof Problems" document.)

-
Do you know a "~100% bijective" proof of Claim 1? Since Stanley's Bijective Proof Problems mentions this problem as solved, such a proof should exist. –  Gábor V. Nagy Jun 17 '12 at 17:15
@GáborV.Nagy: No, I don't. The only proof I know is the one I came up with. –  Mike Spivey Jul 20 '12 at 21:15
This is an amazingly . . . sophisticated proof. +1 –  Soham Chowdhury Oct 13 '14 at 15:39

My alternative solution can be found here (in Section 4), by counting paths: http://arxiv.org/abs/1204.5923

-
+1. Interesting! –  Mike Spivey Jul 20 '12 at 21:12