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, When *n* is odd, the left-hand side evaluates to .

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, , 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 to get

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 of uniformly at random. For each cycle *w* of color *w* red with probability ; otherwise, color it blue. This creates a colored permutation . Then is the probability that exactly *k* of the *n* elements of a randomly-chosen permutation are colored red.

**Right-hand side:** Select a permutation of uniformly at random. Then, if *n* is even, is the probability that contains only cycles of even length.

**Connecting argument: ** For any colored permutation , find the smallest element of contained in an odd-length cycle *w* of . Let be the colored permutation for which the color of *w* is flipped. Then , and and 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 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 , 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 , so the left-hand side must equal the probability of selecting a permutation of uniformly at random and obtaining one containing only cycles of even length. Therefore,

(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**

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