What is the combinatorial intepretation to this identity? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T08:29:59Z http://mathoverflow.net/feeds/question/21202 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/21202/what-is-the-combinatorial-intepretation-to-this-identity What is the combinatorial intepretation to this identity? Sunni 2010-04-13T13:34:56Z 2010-04-18T10:57:18Z <p>I came across the following combinatorial identity in a paper 'a remarkable sequence of integers'. </p> <p> $\sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m} =4^{-m} \binom{4m+1}{2m}.$ </p> <p>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.</p> <p>My elementary proof is through the method of coefficients.</p> <p>Let $[t^n]f(t)$ be the coefficient of $t^n$ in $f(t)$.</p> <p><strong>Lemma:</strong> $[t^k]\frac{1}{\sqrt{1-t}}=4^{-k} \binom{2k}{k}$.</p> <p><strong>Proof:</strong> </p> <p> \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} </p> <p>QED</p> <p>Moreover, it is easy to see</p> <p> \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} </p> <p><strong>Proposition:</strong></p> <p>$$\sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m}= 4^{-m} \binom{4m+1}{2m}.$$</p> <p><strong>Proof:</strong> </p> <p> \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} </p> <p>QED</p> http://mathoverflow.net/questions/21202/what-is-the-combinatorial-intepretation-to-this-identity/21312#21312 Answer by Martin Rubey for What is the combinatorial intepretation to this identity? Martin Rubey 2010-04-14T06:21:26Z 2010-04-14T06:21:26Z <pre> (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 </pre> <p>what am I missing?</p> http://mathoverflow.net/questions/21202/what-is-the-combinatorial-intepretation-to-this-identity/21369#21369 Answer by Jason Dyer for What is the combinatorial intepretation to this identity? Jason Dyer 2010-04-14T18:02:39Z 2010-04-14T18:02:39Z <p>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:</p> <p>Imagine you have a set of <em>n</em> 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.</p> <p>Exactly 1/2 of them must have exactly one boy. The remaining single-child families must have girls.</p> <p>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)<em>n</em> families to have two children.)</p> <p>Without the $2^{-2k}$ term, the LHS enumerates the possible sets of families that follow the conditions above given $2m=n$.</p> <p>With the $2^{-2k}$ term, there's an additional condition in enumerating: take the configurations that involve <em>r</em> two-child families, say there's <em>c</em> of them. Form the ratio between <em>c</em> and the total ways the genders of the two-child families could come out if it <em>wasn't</em> an equal number of boys and girls. The sum of all ratios for all values of <em>r</em> from 0 to (1/2)<em>n</em> achieves the LHS described in the equation.</p> http://mathoverflow.net/questions/21202/what-is-the-combinatorial-intepretation-to-this-identity/21731#21731 Answer by Sune Jakobsen for What is the combinatorial intepretation to this identity? Sune Jakobsen 2010-04-18T10:57:18Z 2010-04-18T10:57:18Z <p>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.</p> <p>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. </p> <p>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}$. </p> <p>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}&lt;2^{2m}\binom{2m}{m}$). Perhaps you should try to ask this in you question?</p>