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.)
 A: My alternative solution can be found here (in Section 4), by counting paths: http://arxiv.org/abs/1204.5923
A: 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.)
