Una identidad binomial a partir de contar permutaciones con ciclos de longitud dos.

Question

Dejemos que $n\ge 1$ sea un número entero. Consideremos la siguiente secuencia:

donde $\left\{l_j\right\}_{j=1}^n$ Al analizar todas las posibles descomposiciones de la secuencia anterior en pares distintos hemos descubierto la siguiente identidad: \begin{equation} n!\sum\limits_{j=0}^{\lfloor \frac{n}{2} \rfloor}\frac{(2j-1)!!}{2^j j!} \binom{n}{2 j} = (2n-1)!! \end{equation} Tenga en cuenta que el $j$ en la suma es igual al número de descomposiciones en pares donde hay exactamente $j$ donde el primer y el último elemento del parw son ambos ceros.

Ahora, mi pregunta sería si hay alguna forma alternativa de probar esta identidad, tal vez utilizando métodos analíticos.

Answer 1

El enfoque general para abordar estas cuestiones es el algoritmo de la hermana Celine. Se puede demostrar que siempre que el término bajo la suma sea una función hipergeométrica, entonces ese término satisface una cierta relación de recursión lineal. Para ser más específicos, denotemos: \begin{equation} F[n,k] := n! \frac{(2k-1)!! }{2^k k!} \binom{n}{2 k} \end{equation} entonces existe una relación de recursión lineal de la forma \begin{equation} \sum\limits_{i=0}^I \sum\limits_{j=0}^J a_{i,j} F[n-i,k-j] = 0 \end{equation} para algunos valores de $I,J$ . En la práctica, la búsqueda de los coeficientes es la siguiente. En primer lugar, se asumen ciertos valores enteros para $I,J$ . En segundo lugar, divide el lado izquierdo por $F[n,k]$ llevar toda la expresión a un denominador común y simplificar para reducirla a una forma polinómica. En tercer lugar, expresa el numerador como un polinomio en $k$ ponerlo a cero y resolver los coeficientes desconocidos $a_{i,j}$ . Si no hay una solución distinta de cero, entonces vuelve al principio y empieza con algunos valores mayores de $I,J$ . En nuestro caso es $I=2$ y $J=1$ producir una solución no nula. En otras palabras, tenemos: \begin{equation} -F[n-1,k](2n-1)+F[n-2,k] (n-1)^2 - F[n-2,k-1](n-1)^2 + F[n,k] =0 \end{equation} Ahora definimos nuestra suma como $S[n] := \sum\limits_{k=0}^\infty F[n,k]$ . Entonces, a partir de la recursión anterior tenemos: \begin{equation} -S[n-1] (2n-1) + S[n] =0 \end{equation} con sujeción a $S[1]=1$ . Esto da claramente $S[n] = (2n-1)!!$ como debería ser.

Answer 2

Supongamos que intentamos demostrar que

$$n! \sum_{q=0}^{\lfloor n/2 \rfloor} \frac{(2q-1)!!}{2^q q!} {n\choose 2q} = (2n-1)!!,$$

que es

$$n! \sum_{q=0}^{\lfloor n/2 \rfloor} \frac{1}{2^q q!} \frac{(2q)!}{2^q q!} {n\choose 2q} = \frac{(2n)!}{2^n n!}$$

o

$$\sum_{q=0}^{\lfloor n/2 \rfloor} \frac{1}{4^q} {2q\choose q} {n\choose 2q} = \frac{1}{2^n} {2n\choose n}.$$

Ahora tenemos

$${2q\choose q} {n\choose 2q} = \frac{n!}{q!\times q!\times (n-2q)!} = {n\choose q} {n-q\choose q}.$$

El LHS se convierte en

$$\sum_{q=0}^{\lfloor n/2 \rfloor} \frac{1}{4^q} {n\choose q} {n-q\choose n-2q}$$

e introducimos

$${n-q\choose n-2q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-2q+1}} (1+z)^{n-q} \; dz$$

Esto controla el alcance y se desvanece cuando $2q\gt n$ por lo que podemos ampliar $q$ a $n$ , obteniendo por la suma

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n} \sum_{q=0}^n \frac{1}{4^q} {n\choose q} \frac{z^{2q}}{(1+z)^q} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n} \left(1+\frac{z^2}{4(1+z)}\right)^n \; dz \\ = \frac{1}{4^n} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (z+2)^{2n}\; dz.$$

Extrayendo los coeficientes encontramos

$$\frac{1}{4^n} {2n\choose n} 2^n$$ que es

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2^n} {2n\choose n}}$$

como se ha reclamado.