69 votos

Combinatoria prueba de que $\sum \limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$ al $n$ es incluso

En mi respuesta aquí puedo demostrar, usando las funciones de generación, una declaración equivalente a $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$$ al $n$ es incluso. (Claramente la suma es $0$ al $n$ es impar.) La bonita expresión en el lado derecho indica que no debería ser muy combinatoria prueba de esta afirmación. La prueba debe comenzar por la asociación de objetos con paridad par y objetos con paridad impar, contado por el lado izquierdo. El número de restos (no) los objetos deben tener incluso la paridad y debe "obviamente" ser $2^n \binom{n}{n/2}$. Estoy teniendo problemas para encontrar una prueba, aunque. Entonces, mi pregunta es

Alguien puede producir una combinatoria prueba de que, incluso para $n$, $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}?$$

Algunos pensamientos hasta el momento:

Combinatoria pruebas para $\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n$ se dan por Phira aquí y por Brian M. Scott aquí. Las pruebas son básicamente equivalentes. En Phira del argumento, ambos lados contar el número de caminos de longitud $2n$ a partir de $(0,0)$ el uso de los pasos de $(1,1)$$(1,-1)$. Por el condicionamiento en el mayor valor de $2k$ para que una determinada ruta devuelve al eje horizontal en $(2k,0)$ y el uso de los hechos que allí se $\binom{2k}{k}$ rutas de $(0,0)$ $(2k,0)$ $\binom{2n-2k}{n-k}$caminos de longitud $2n-2k$ que se inician en el eje horizontal, pero nunca vuelven al eje obtenemos el lado izquierdo.

Con estas interpretaciones de la central de los coeficientes binomiales $2^n \binom{n}{n/2}$ puede contar (1) rutas de acceso que no vuelva a hacer el eje horizontal de la ruta de acceso del punto a mitad de camino de $(n,0)$, o (2) rutas de acceso que toque el punto de $(n,0)$. Pero no he sido capaz de construir la asociación que hace que estos los restos de caminos (no todos estos caminos tienen incluso la paridad de todos modos). Así que tal vez hay alguna otra interpretación de $2^n \binom{n}{n/2}$ a medida que el número de restos de caminos.


La actualización. Más pensamientos:

No hay otra manera de ver la identidad $\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n$. Ambos lados contar el número de celosía de caminos de longitud $n$ al norte, sur, este y oeste pasos están permitidos. El lado derecho es evidente. El lado izquierdo tiene una interpretación similar como antes: $\binom{2k}{k}$ cuenta el número de NSEW entramado de caminos de longitud $k$ que terminan en la línea de $y=0$, e $\binom{2n-2k}{n-k}$ cuenta el número de NSEW entramado de caminos de longitud $n-k$ que nunca volver a la línea de $y =0$. Hasta ahora, esto no es mucho más diferente como antes. Sin embargo, $2^n \binom{n}{n/2}$ tiene una interesante interpretación: Se cuenta el número de NSEW entramado de caminos que terminan en la diagonal $y = x$ (o, equivalentemente, $y = -x$). Así que tal vez hay una involución que deja a estos como el resto de las rutas. (Pruebas de todas estas afirmaciones se pueden encontrar en este blog, para aquellos que estén interesados.)

26voto

Martin OConnor Puntos 116

Dividir por $4^n$, de modo que la identidad lee (de nuevo, para $n$ incluso)

$$ \sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n} (-1)^k = \frac{1}{2^n} \binom{n}{n/2}. \tag{1}$$

Reivindicación 1: Seleccione una permutación $\sigma$ $[n]$ uniformemente al azar. Para cada ciclo de $w$$\sigma$, color $w$ rojo, con probabilidad de $1/2$; de lo contrario, de color azul. Esto crea un color de permutación $\sigma_C$. Entonces $$\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$ son de color rojo. (Ver la prueba de la Reivindicación 1 a continuación).

Reivindicación 2: Seleccione una permutación $\sigma$ $[n]$ uniformemente al azar. Entonces, si $n$ es incluso, $$\frac{1}{2^n} \binom{n}{n/2}$$ is the probability that $\sigma$ contiene sólo los ciclos de longitud. (Ver la prueba de la Reivindicación 2 a continuación).

Combinatoria prueba de $(1)$, dadas las Reivindicaciones 1 y 2: Para cualquier color de permutación $\sigma_C$, encontramos el elemento más pequeño de $[n]$ contenida en una longitud impar ciclo de $w$$\sigma_C$. Deje $f(\sigma_C)$ ser el color de permutación para que el color de $w$ es volteado. A continuación,$f(f(\sigma_C)) = \sigma_C$, e $\sigma_C$ $f(\sigma_C)$ tienen diferentes partidos para el número de elementos de color rojo, pero la misma probabilidad de ocurrencia. Por lo tanto $f$ es una señal de-revertir la involución en el color de permutaciones para que $f$ está definido. El único color permutaciones $\sigma_C$ que $f$ no está definido son los que sólo tienen incluso la duración de los ciclos. Sin embargo, cualquier permutación con un número impar de elementos de color rojo debe tener al menos una longitud impar ciclo, por lo que el único color permutaciones para que $f$ no está definido tiene un número par de elementos de color rojo. Por lo tanto el lado izquierdo de $(1)$ debe ser igual a la probabilidad de elegir un color de permutación que contiene sólo la longitud de los ciclos. La probabilidad de seleccionar uno de los varios colores variantes de un determinado incoloro permutación $\sigma$, sin embargo, es que de la elección de un incoloro permutación uniformemente al azar y la obtención de $\sigma$, de modo que el lado izquierdo de $(1)$ debe ser igual a la probabilidad de selección de una permutación de $[n]$ uniformemente al azar y la obtención de una que contiene sólo los ciclos de longitud. Por lo tanto, $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n} (-1)^k = \frac{1}{2^n} \binom{n}{n/2}.$$

(Claramente, $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} \frac{1}{4^n} = 1,$$ que le da otro combinatoria prueba de la unsigned versión de $(1)$ mencionado en la pregunta.)


Prueba de Reclamación 1: Hay $\binom{n}{k}$ formas de elegir que $k$ elementos de una permutación será de color rojo y que $n-k$ elementos será de color azul. Dado $k$ elementos particulares de $[n]$, el número de maneras en que los $k$ elementos puede ser expresado como el producto de la $i$ ciclos disjuntos es $\left[ {k \atop i} \right]$, unsigned número de Stirling de primera especie. Por lo tanto la probabilidad de elegir una permutación $\sigma$ que tiene los $k$ elementos como el producto de la $i$ ciclos disjuntos y el resto de $n-k$ elementos como el producto de la $j$ ciclos disjuntos es $\left[ {k \atop i} \right] \left[ {n-k \atop j}\right] /n!$, y la probabilidad de que el $i$ de los ciclos son de color rojo y el $j$ de los ciclos son de color azul, así es $\left[ {k \atop i} \right] \left[ {n-k \atop j}\right]/(2^i 2^j n!).$ resumiendo, la probabilidad de que exactamente $k$ de la $n$ elementos escogidos al azar de permutación son de color rojo es \begin{align} \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}. \end{align} La suma de dos son básicamente la misma, tan sólo tendremos que hacer la primera. $$\sum_{i=1}^k \frac{\left[ {k \atop i} \right]}{2^i} = \left( \frac{1}{2} \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!}.$$ (La primera igualdad es la conocida propiedad de que los números de Stirling de primera especie se utilizan para convertir aumento de los factoriales de los poderes de competencias ordinarias. Esta propiedad puede ser demostrado de forma combinatoria. Por ejemplo, Vol. 1 de Richard Stanley Combinatoria Enumerativa, 2ª ed., pp 34-35 contiene dos combinatoria de las pruebas.)

Por lo tanto la probabilidad de que exactamente $k$ de la $n$ elementos de un elegido al azar de permutación son de color rojo es $$\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}.$$


La prueba de la Reivindicación 2: Ya que no puede haber ciclos impares, $\sigma(1) \neq 1$. Por lo tanto, hay $n-1$ opciones para $\sigma(1)$. Ya hemos elegido el elemento que se asigna a $\sigma(1)$, pero de lo contrario no hay restricciones sobre el valor de $\sigma(\sigma(1))$, y así tenemos el $n-1$ opciones para $\sigma(\sigma(1))$.

Ahora $n-2$ elementos están sin asignar. Si $\sigma(\sigma(1)) \neq 1$, entonces tenemos un ciclo abierto. No podemos asignar $\sigma^3(1) = 1$, como que iba a cerrar el ciclo actual en un número impar de elementos. También, $\sigma(1)$ $\sigma^2(1)$ ya están tomadas. Por lo tanto, hay $n-3$ opciones para el valor de $\sigma^3(1)$. Si $\sigma(\sigma(1)) = 1$, entonces ya hemos cerrado un ciclo par. La selección de cualquier asignada elemento en $[n]$, decir $j$, no podemos tener a $\sigma(j) = j$, ya que crearía un ciclo impar, y $1$ $\sigma(1)$ ya están tomadas. Así tenemos a $n-3$ opciones para $\sigma(j)$.

En general, si hay $i$ elementos sin asignar y $i$ es incluso, no es de uno, incluso de longitud de ciclo abierto o no abrir los ciclos. Si hay un ciclo abierto, no se pueden cerrar, y así tenemos el $i-1$ opciones para el siguiente elemento en el ciclo. Si no hay un ciclo abierto, seleccionamos a los más pequeños sin asignar el elemento $j$. Ya que no podemos tener $\sigma(j) = j$, $i-1$ opciones para $\sigma(j)$. De cualquier manera, nos ha $i-1$ opciones. Si hay $i$ elementos sin asignar y $i$ es extraño, sin embargo, no debe ser siempre un número impar de longitud de ciclo abierto. Ya podemos cerrar, hay $i$ opciones para el siguiente elemento en el ciclo.

Todos juntos, entonces, si $n$ es incluso entonces, el número de permutaciones de $[n]$ que sólo contienen ciclos de longitud es $$(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 $$\frac{1}{2^n} \binom{n}{n/2}.$$


(He estado pensando acerca de este problema y en el de dos meses desde la primera vez que lo publicó. Lo que finalmente partió para mí fue el descubrimiento de la interpretación de la unsigned versión de la identidad menciona como #60 en Richard Stanley "Bijective Prueba de Problemasde este documento.)

7voto

Gábor V. Nagy Puntos 196

Mi alternativa de solución se puede encontrar aquí (en la Sección 4), contando con rutas de acceso: http://arxiv.org/abs/1204.5923

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X