Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.)

share|improve this question
2  
I have set a bounty for this problem. After trying for some time, I feel that "new" (to me :-)) techniques might be necessary to handle the cancelations among the terms. I am especially interested in an inclusion-exclusion based proof, which I believe should exist. –  Srivatsan Dec 6 '11 at 7:35
2  
I was thinking of a more "literal" interpretation of the RHS. I was thinking of the number of paths from (0,0) to (n/2,n/2) whereby each step is colored in one of two colors. The part I find difficult to think about is the LHS. Since each path has n edges and thus n colors, we can represent the coloring with 2n characters, which connects the LHS to the RHS (as the top binomial coefficients add to 2n in the LHS) but I fail to see how to continue. –  picakhu Dec 7 '11 at 15:45
2  
Here's one tantalizing bit of cancellation: Start with Phira's interpretation (the LHS counts walks which return to $0$ for the last time at time $2k$). Fix any odd $t$, and consider all walks which return to $0$ for the first time at $2t$. The sum over all such walks is $0$, since after conditioning on the first $2t$ steps we're effectively left with the same sum over walks of length $2(n-t)$ and $n-t$ is odd. So the left hand side can be thought of as counting walks which never return to $0$ at a time in $\{2,6,10,14,\dots, 2n-2\}$. (continued in next comment) –  Kevin Costello Dec 8 '11 at 8:46
2  
Conversely, as noted in the original post, the right hand side can be thought of as walks which never return to $0$ at a time in $\{2,4,6,8,\dots, n\}$. Similar in form, but I still don't see a direct bijection between them. –  Kevin Costello Dec 8 '11 at 8:48
3  
The bounty I have set for this question has expired. However to encourage further progress on this problem, I hereby announce an unofficial “lifelong” bounty of +300 reps. (Once an answer is posted, I will start the bounty to reward it.) Note however that the bounty will be cancelled immediately if the OP takes the question over to MO. –  Srivatsan Dec 14 '11 at 9:53
show 15 more comments

2 Answers 2

up vote 14 down vote accepted

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.)

share|improve this answer
    
Do you know a "~100% bijective" proof of Claim 1? Since Stanley's Bijective Proof Problems mentions this problem as solved, such a proof should exist. –  Gábor V. Nagy Jun 17 '12 at 17:15
    
@GáborV.Nagy: No, I don't. The only proof I know is the one I came up with. –  Mike Spivey Jul 20 '12 at 21:15
add comment

My alternative solution can be found here (in Section 4), by counting paths: http://arxiv.org/abs/1204.5923

share|improve this answer
    
+1. Interesting! –  Mike Spivey Jul 20 '12 at 21:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.