¿Existe una interpretación combinatoria de la identidad$\sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m} =4^{-m} \binom{4m+1}{2m}$?

Question

Me encontré con la siguiente combinatoria de la identidad en un papel por Victor H. Moll y Dante V. Manna 'una notable secuencia de enteros'.

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

Me dio una primaria de la prueba en lo que sigue, sin embargo, una interpretación combinatoria parece difícil para un profano como yo. Así que a publicar aquí para la discusión.

Mi primaria la prueba es a través del método de los coeficientes.

Deje $[t^n]f(t)$ ser el coeficiente de $t^n$ en $f(t)$.

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

Prueba:

$$ \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

Por otra parte, es fácil ver

$$ \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} $$

La proposición:

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

Prueba:

$$ \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 1

No tengo una respuesta, pero he de pasar un par de horas, así que aquí hay algunos de mis pensamientos sobre el problema.

En la siguiente voy a identificar las expresiones de conjuntos, por lo $2^n$ corresponde al conjunto de 01-secuencias de longitud n, $\binom{n}{k}$ es el conjunto de 01-secuencia de longitud n con exactamente k 1s, y los productos y sumas corresponde a la toma de conjuntos de productos, y de los sindicatos.

Queremos encontrar un bijective función de $\sum_{k=0}^m 2^{2(m-k)} \binom{2k}{k} \binom{2m-k}{m}$ a $\binom{4m+1}{2m}$ I se han multiplicado con $4^m$ en ambos lados). Permítanme darles un ejemplo de una apariencia similar a la igualdad (puede omitir el resto de este párrafo, si lo desea): $\sum_{k=0}^m2^{2(m-k)}\binom{2k}{k}\binom{2m}{2k}=\binom{4m}{2m}$. Tomar un elemento en $\binom{4m}{2m}$, y a la par de los términos, por lo que tenemos una secuencia de más de {(00),(01),(10),(11)} de longitud $2m$. Tenemos un número par de 1s en la secuencia, por lo que debe haber un número par de pares que contienen exactamente un 1, y por lo tanto e incluso el número de pares con (00) o (11). Deje que el número de (00) y (11) en la secuencia de pares de ser 2k. Ahora k de estos debe ser (00) y k de ellos es (11) es el número de 0s y 1s son los mismos. El 2k en términos de 2m de longitud de la secuencia puede ser elegido en $\binom{2m}{2k}$ formas, el k (11)s de estos 2k términos pueden elegido en $\binom{2k}{k}$ formas y en el resto de la $2m-2k$ términos debemos elegir entre (10) y (01). Esto le da un factor de $2^{2(m-k)}$, por lo que tenemos una correspondencia 1-1 entre el $\sum_{k=0}^m2^{2(m-k)}\binom{2k}{k}\binom{2m}{2k}$ e $\binom{4m}{2m}$.

Una parte importante de dicha prueba es averiguar lo k representa. En su igualdad, resulta que k=0 la parte de la suma se acerca $\sqrt{\frac{1}{2}}$ de la suma total. ¿Alguien sabe donde la $\sqrt{\frac{1}{2}}$ podría provenir? Una manera de averiguar lo k es, sería encontrar una función inyectiva de la k=0 plazo, $2^{2m}\binom{2m}{m}$, a $\binom{4m+1}{2m}$ y ver lo que el conjunto de imágenes se ve como. Pero no he sido capaz de encontrar una función de este tipo, que es, no puedo encontrar una combinatoria prueba de que $2^{2m}\binom{2m}{m}\leq \binom{4m+1}{2m}$ (ni que $\binom{4m}{2m}<2^{2m}\binom{2m}{m}$). Tal vez usted debe tratar de hacer esto en usted pregunta?

Answer 2

Desde que usted se describe como un "laico" supongo que usted no quiere oír acerca de la medida de Haar en Grassmannian espacio G(n,1), así que aquí está mi mejor explicación intuitiva de la parte izquierda de la ecuación combinatorically:

Imagine que usted tiene un conjunto de n familias. Cada familia cuenta con 1 o 2 niños. Los dos hijos de las familias tienen un mayor y un menor, de modo que los niños son distinguibles.

Exactamente 1/2 de ellos debe tener exactamente la de un chico. El resto de hijo único familias deben tener las niñas.

De los dos hijos, familias, cuando el recuento de todos los niños y niñas debe haber un número igual de niños y niñas. (Es posible que 0 familias de hasta (1/2)n a las familias a tener dos hijos.)

Sin el $2^{-2k}$ plazo, la LHS enumera los posibles conjuntos de familias que siguen las condiciones anteriores $2m=n$.

Con la $2^{-2k}$ plazo, hay una condición adicional en enumerar: tomar las configuraciones que implican r de dos hijos, familias, dicen que no hay c de ellos. Forma de la relación entre el c y el total de maneras en que el género de la dos-hijos de las familias podría salir si no era un número igual de niños y niñas. La suma de todos los coeficientes para todos los valores de r de 0 a (1/2)n alcanza el LHS se describe en la ecuación.