What is the combinatorial intepretation to this identity? - MathOverflow

What is the combinatorial intepretation to this identity?

2010-04-13T13:34:56Z

I came across the following combinatorial identity in a paper 'a remarkable sequence of integers'.

$\sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m} =4^{-m} \binom{4m+1}{2m}. $

I gave an elementary proof as follows, yet I a combinatorial intepretation seems difficult to a layman like me. So I post it here for discussion.

My elementary proof is through the method of coefficients.

Let $[t^n]f(t)$ be the coefficient of $t^n$ in $f(t)$.

Lemma: $[t^k]\frac{1}{\sqrt{1-t}}=4^{-k} \binom{2k}{k}$.

Proof:

$$ \begin{aligned} [t^k]\frac{1}{\sqrt{1-t}} &=\binom{-1/2}{k} (-1)^k \\\\ &=\binom{1/2+k-1}{k} \\\\ &=\frac{(k-1/2)(k-3/2)\cdots (1/2)}{k!}\\\\ &=\frac{(2k-1)(2k-3)\cdots 1}{k!}2^{-k} \\\\ &=\frac{(2k)(2k-1)(2k-2)(2k-3)\cdots 2\cdot1}{k!\cdot k!} 4^{-k} \\\\ &= 4^{-k} \binom{2k}{k} \end{aligned} $$

QED

Moreover, it is easy to see

$$ \begin{aligned} \binom{2m-k}{m}&=\binom{2m-k}{m-k} \\\\ &=\binom{-(2m-k)+m-k-1}{m-k}(-1)^{m-k}\\\\ &= \binom{-m-1}{m-k} (-1)^{m-k} \\\\ &=[t^{m-k}]\frac{1}{(1-t)^{m+1}} \end{aligned} $$

Proposition:

$$\sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m}= 4^{-m} \binom{4m+1}{2m}.$$

Proof:

$$ \begin{aligned} \sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m} &= [t^m]\left(\frac{1}{\sqrt{1-t}} \frac{1}{(1-t)^{m+1}}\right) \\\\ &= [t^m]\frac{1}{(1-t)^{m+(3/2)}} \\\\ &=\binom{-m-(3/2)}{m} (-1)^m \\\\ &=\binom{2m+(1/2)}{m} \\\\ &= 2^{-m} \frac{(4m+1)(2m-1)\cdots(2m+3)}{m!} \\\\ &=2^{-m} \frac{(4m+1)(2m-1)\cdots(2m+3)}{m!} \frac{4m(4m-2)\cdots(2m+2)}{4m(4m-2)\cdots(2m+2)} \\\\ &=2^{-2m}\frac{(4m+1)!}{(2m+1)!(2m)!} \\\\ &=2^{-2m} \binom{4m+1}{2m} \end{aligned} $$

QED

Answer by Martin Rubey for What is the combinatorial intepretation to this identity?

2010-04-14T06:21:26Z

(1) -> [4^(-m)*binomial(4*m+1, 2*m) for m in 1..10]

   (1)
    5 63 429 12155 88179 1300075 9694845 583401555 4418157975 67282234305
   [-,--,---,-----,-----,-------,-------,---------,----------,-----------]
    2  8  16  128   256    1024    2048    32768      65536      262144

what am I missing?

Answer by Jason Dyer for What is the combinatorial intepretation to this identity?

2010-04-14T18:02:39Z

Since you describe yourself as a "layman" I'm guessing you don't want to hear about the Haar measure on Grassmannian space G(n,1), so here's my best intuitive explanation of the left hand side of the equation combinatorically:

Imagine you have a set of n families. Each family has either 1 or 2 children. The two-child families have an older and a younger child, so the children are distinguishable.

Exactly 1/2 of them must have exactly one boy. The remaining single-child families must have girls.

Of the two-child families, when counting up all the boys and girls together there must be an equal number of boys and girls. (It's possible for 0 families up to (1/2)n families to have two children.)

Without the $2^{-2k}$ term, the LHS enumerates the possible sets of families that follow the conditions above given $2m=n$.

With the $2^{-2k}$ term, there's an additional condition in enumerating: take the configurations that involve r two-child families, say there's c of them. Form the ratio between c and the total ways the genders of the two-child families could come out if it wasn't an equal number of boys and girls. The sum of all ratios for all values of r from 0 to (1/2)n achieves the LHS described in the equation.

Answer by Sune Jakobsen for What is the combinatorial intepretation to this identity?

2010-04-18T10:57:18Z

I don't have an answer, but I have spend a couple of hours on it, so here is some of my thoughts on the problem.

In the following I will identify expressions with sets, so $2^n$ corresponds to the set of 01-sequences of length n, $\binom{n}{k}$ is the set of 01-sequence of length n with exactly k 1s, and products and sums corresponds to taking product sets and unions.

We want to find a bijective function from $\sum_{k=0}^m 2^{2(m-k)} \binom{2k}{k} \binom{2m-k}{m}$ to $\binom{4m+1}{2m}$ (I have multiplied with $4^m$ on both sides). Let me give an example a similar looking equality (you can skip the rest of this paragraph if you want): $\sum_{k=0}^m2^{2(m-k)}\binom{2k}{k}\binom{2m}{2k}=\binom{4m}{2m}$. Take an element in $\binom{4m}{2m}$, and pair the terms, so we have a sequence over {(00),(01),(10),(11)} of length $2m$. We have an even number of 1s in the sequence, so there must be an even number of pairs that contain exactly one 1, and thus and even number of pairs with (00) or (11). Let the number of (00) and (11) in the sequence of pairs be 2k. Now k of these must be (00) and k of them is (11) is the number of 0s and 1s are the same. The 2k terms in the 2m length sequence can be chosen in $\binom{2m}{2k}$ ways, the k (11)s of these 2k terms can chosen in $\binom{2k}{k}$ ways and in the rest of the $2m-2k$ terms we must choose between (10) and (01). This gives a factor $2^{2(m-k)}$, so we have a 1-1 correspondence between $\sum_{k=0}^m2^{2(m-k)}\binom{2k}{k}\binom{2m}{2k}$ and $\binom{4m}{2m}$.

An important part of such a proof is to find out what k represents. In your equality, it turns out that the k=0 part of the sum is about $\sqrt{\frac{1}{2}}$ of the whole sum. Do anyone know where the $\sqrt{\frac{1}{2}}$ could come from? One way to find out what k is, would be to find an injective function from the k=0 term, $2^{2m}\binom{2m}{m}$, to $\binom{4m+1}{2m}$ and see what the image set looks like. But I haven't been able to find such a function, that is, I cannot find a combinatorial proof that $2^{2m}\binom{2m}{m}\leq \binom{4m+1}{2m}$ (nor that $\binom{4m}{2m}<2^{2m}\binom{2m}{m}$). Perhaps you should try to ask this in you question?