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.
Advertisements
This entry was posted in binomial coefficients, combinatorics. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s