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.)
