Combinatorial Interpretation of the Alternating Convolution of the Central Binomial Coefficients, Part 2

In my last post I talked about how to interpret the following formula combinatorially:

\displaystyle \sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}.

I skipped some parts of the argument, though.  I gave the bijection relating a combinatorial interpretation of the left-hand side with a combinatorial interpretation of the right-hand side, but I did not justify the interpretations of the two sides themselves.  This post will do that.  (As with my previous post, this is pretty much lifted from my answer to one of my own math.SE questions.)


Left-hand side interpretation: 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.

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

The two sums on the right-hand side are basically the same, so we’ll just do the first one.
\displaystyle \sum_{i=1}^k \frac{\left[ {k \atop i} \right]}{2^i} = \left(\frac{1}{2} + i\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* [1], 2nd ed., pp. 33-34, contains two such combinatorial proofs.)

Thus the probability that exactly k of then elements of a randomly chosen permutation are colored red is \displaystyle \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}.


Right-hand side interpretation: 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.

Proof:  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 cannot 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 any 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 arei 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 \displaystyle (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 \displaystyle\frac{1}{2^n} \binom{n}{n/2}.


References

  1. Richard Stanley, Enumerative Combinatorics, 2nd ed., Cambridge University Press, 2011.
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