Número de involución en el grupo simétrico

Question

Puede mostrarme en cómo probar que el número de involuciones en el grupo simétrico de a $n$ letras, $$\sum_{k=0}^{\lfloor n/2 \rfloor} {n \choose 2k} (2k-1)!! = \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{n!}{2^kk!(n-2k)!}$$

He tratado de demostrar que a través de Pequeños cuadros, sabiendo que el número de viñetas es el número de involuciones, pero no tengo el derecho de respuesta hasta el momento.

Answer 1

Deje $\tau$ ser una involución. Escrito $\tau$ como producto de ciclos disjuntos, vemos que no hay ciclo puede tener una longitud mayor de $3$ desde $\tau$ orden $2$. De ello se desprende que $\tau$ es un producto de distintos transposiciones.

Supongamos que $\tau$ es un producto de $k$ discontinuo transposiciones. Entonces permutes, precisamente, $2k$ letras así que debemos elegir las letras de la a $n$ disponible. A continuación, debemos grupo de la $2k$ letras en $k$ pares. No son precisamente $$a_k = \binom{n}{2k}\frac{(2k)!}{k!2^k} = \binom{n}{2k}(2k-1)!!$$ maneras de hacer esto así que no son, precisamente, $a_k$ involuciones con $k$ discontinuo transposiciones.

Claramente $k$ puede variar de $0$ (la identidad) a $\lfloor \frac{n}{2}\rfloor$ transposiciones. Sumando a través de los diferentes valores de $a_k$ da el resultado deseado.

Answer 2

Este parece ser explicado en este artículo de la wikipedia.