La identidad de la convolución de la central de los coeficientes binomiales

Question

No es difícil mostrar que

$$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$

Por otro lado, tenemos a $(1-z^2)^{-1}=\sum z^{2n}$. El cuadrado de la primera potencia de la serie y la comparación de los términos nos da

$$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}2^{-2n}=1$$

es decir,

$$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$$

Mi pregunta: ¿hay una manera más directa, combinatoria prueba de esta identidad? He sido el tormento de mi cerebro tratando de encontrar uno, pero no estoy teniendo mucho éxito.

Answer 1

Es posible dar un directo combinatoria prueba, pero es muy difícil encontrarlo.

Una posibilidad es utilizar las rutas entre puntos con coordenadas enteras y los pasos a $(1,1)$$(1,-1)$.

1) $\binom{2n}{n}$ cuenta todas las rutas de$(0,0)$$(2n,0)$.

2) $2^{2n}$ cuenta todas las rutas a partir de $(0,0)$ $2n$ pasos.

3) $\binom{2n}{n}$ cuenta todas las rutas con $2n$ pasos que nunca toque el $x$-eje de nuevo después de su inicio. (Este no es evidente, pero puede ser demostrado con un bijection.)

Ahora se puede concluir que todos los caminos son una concatenación de un camino que devuelve un determinado número de veces a la $x$-eje y un camino que nunca lo hace.

Tenga en cuenta que la principal dificultad aquí es que los dos coeficientes binomiales son interpretadas de manera diferente.

Editado para añadir la referencia: En Richard P. Stanley: la Combinatoria Enumerativa el Volumen 1, Capítulo 1, la Solución a prueba 2c la siguiente referencia:

El problema de dar una combinatoria prueba fue planteado por P. de Veress y resuelto por G. Hajos en la década de 1930. Una prueba reciente aparece en D. J. Kleitman, los Estudios en Matemáticas Aplicadas. 54 (1975), 289 - 292. Véase también M. Sved, Matemáticas. Intelligencer, vol.6, no. 4 (1984), 44-45.

Pero no he mirado para comprobar que el artículo da la prueba de que he descrito anteriormente.

Answer 2

He aquí otra prueba, que estoy ligeramente prefiere. Voy a empezar con la parte más difícil.

Lema. El número de todas las palabras de longitud $n$ en el alfabeto $\{A,B\}$ de tal manera que ningún prefijo (a la izquierda factor) contiene más letras de $B$$A$$\binom n{\lceil n/2\rceil}$.

En lugar de estas palabras que uno también puede tomar, la interpretación de $A$ como un paso y $B$ como un paso, rutas de acceso como en la respuesta por Phira que nunca pasan por debajo del eje horizontal; o uno puede formular como boleta de secuencias como en Bertand la boleta del problema, con la diferencia de que nos permitir $B$ a ponerse al día con $A$ sin adelantamientos, y que el (no negativo) tamaño de la eventual ventaja de $A$ no es fijo.

Prueba. El siguiente paso puede ser aplicado a cualquier palabra de la que algunos prefijo de no contener más letras de $B$$~A$: encontrar el más pequeño de prefijo para las que la mayoría de sus letras $B$ sobre sus cartas de $A$ es máxima entre todos los prefijos, y el cambio en su última carta (que es un $B$) a $A$. Hay un paso inverso que puede ser aplicado a cualquier palabra con más letras $A$ de las cartas de $B$ (o más generalmente a una palabra de la que algunos sufijo (derecha factor) tiene esta propiedad): encontrar el más pequeño de sufijo para que la mayoría de sus letras $A$ sobre sus cartas de $B$ es máxima entre todos los sufijos, y el cambio en su primera carta (que es un $A$) a $B$. La forma más fácil de ver que estas son operaciones inversas es que la presencia de subpalabras en el Dyck lenguaje para $\{A,B\}$ no tiene ningún efecto sobre estas operaciones (en particular, de que nunca va a cambiar dentro de este tipo de palabras), y que lo que queda cuando se ignoran tales subpalabras es de la forma $BB\ldots BAA\ldots A$, donde el último $B$ respectivamente primera $A$ será cambiado. Ahora, dada una palabra de longitud $n$ $\lceil n/2\rceil$ cartas de $A$ $\lfloor n/2\rfloor$ cartas de $B$, uno puede recorrer la primera operación hasta que el prefijo no contiene más letras de $B$$A$, y a la inversa dada una palabra de longitud $n$ satisfacer esa condición, si no se $d\geq0$ más letras de $A$ $B$ en todos, uno puede repetir la operación inversa $\lfloor d/2\rfloor$ veces para obtener una palabra de longitud $n$ $\lceil n/2\rceil$ cartas de $A$ $\lfloor n/2\rfloor$ cartas de $B$. Este bijection demuestra el lema. QED

Ahora a probar la identidad de la pregunta, considere las palabras de longitud $2n+1$ en el que las letras $A$ son en la mayoría; su número es $2^{2n+1}/2=2^{2n}$. Considerar el prefijo más largo (posiblemente vacía) en el cual existen muchas cartas $A$$B$; tiene una longitud igual a $2k$, y dado que la longitud no se $\binom{2k}k$ posibilidades de este prefijo. La siguiente letra es necesariamente un $A$, y después de eso hay un sufijo de longitud $2n-2k$ en los que no hay ningún prefijo (de ese sufijo) contiene más letras de $B$$A$. Por el lema hay $\binom{2n-2k}{n-k}$ de ellos, de donde el resultado.