## Combinatorial Interpretation of the Alternating Convolution of the Central Binomial Coefficients

Whew, that’s a long title.  Basically, what it says is that this post will give a combinatorial interpretation to the following formula.

When n is even, $\displaystyle \sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}.$  When n is odd, the left-hand side evaluates to $0$.

The formula is not too difficult to prove using generating functions; see, for instance, my answer here.  However, finding a combinatorial interpretation proved difficult.  For a while my question of finding one was the most upvoted unanswered question on math.SE.

The non-alternating version of the formula, $\displaystyle \sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n$, has several nice combinatorial interpretations.  (See, for example, Marta Sved’s article [1].)  Maybe some day I’ll do a post on them.

On to the proof.  First, divide both sides by $4^n$ to get

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

Now we need a combinatorial interpretation of the left- and right-hand sides, as well as a connecting argument between the two.  I’m not going to prove that the combinatorial interpretations of the two sides hold; I’ll save these for my next post.

Left-hand side: 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 $\displaystyle \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.

Right-hand side: Select a permutation $\sigma$ of $[n]$ uniformly at random.  Then, if n is even, $\displaystyle \frac{1}{2^n} \binom{n}{n/2}$ is the probability that $\sigma$ contains only cycles of even length.

Connecting argument:  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 probability-weighted 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 must equal the probability of choosing a colored permutation that contains only even-length cycles.  Given a particular uncolored permutation $\sigma$, though, the sum of the probabilities of choosing one of its colored variants is the probability of choosing an uncolored permutation uniformly at random and obtaining $\sigma$, so the left-hand side must equal the probability of selecting a permutation of $[n]$ uniformly at random and obtaining one containing only cycles of even length.  Therefore,
$\displaystyle \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}.$

(Much of this post is lifted from my answer to my own question of finding a combinatorial interpretation of the alternating convolution of the central binomial coefficients on math.SE.)

References

1. Marta Sved, “Counting and Recounting: The Aftermath,” The Mathematical Intelligencer 6 (1984) 44-45.