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 .) 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.)
- Marta Sved, “Counting and Recounting: The Aftermath,” The Mathematical Intelligencer 6 (1984) 44-45.