Cuántos $\alpha \in S_n$ son tales que $\alpha^2 = 1$ ?

Question

Esto no es para los deberes, pero no se me da muy bien contar argumentos y me gustaría tener alguna opinión. La pregunta es

Dejemos que $n \in \mathbb{N}$ . ¿Cuántos $\alpha \in S_n$ son tales que $\alpha^2 = 1$ ?

Sé que, si $\alpha^2 = 1$ Entonces, o bien $\alpha = 1$ o $\alpha$ es el producto de transposiciones disjuntas.

Si $\alpha = (i, j)$ es una única transposición, entonces hay $\frac{1}{2^1 \cdot 1!} \binom{n}{2}$ tal $\alpha$ (el $2^1$ y $1!$ se ponen en el denominador para ayudar a notar el patrón más tarde).

Si $\alpha = (i, j)(k, l)$ es el producto de $2$ transposiciones disjuntas, entonces hay $\frac{1}{2^2 \cdot 2!} \binom{n}{2} \binom{n-2}{2}$ tal $\alpha$ , donde el $2^2$ aparece en el denominador para dar cuenta de las permutaciones cíclicas de cada transposición, y el $2!$ parece dar cuenta de la permutación de las propias transposiciones.

Si $\alpha$ es el producto de $3$ transposiciones disjuntas, entonces hay $\frac{1}{2^3 \cdot 3!} \binom{n}{2} \binom{n-2}{2} \binom{n-4}{2}$ tal $\alpha$ .

Extrapolando esto, encuentro que el número total de $\alpha \in S_n$ tal que $\alpha^2 = 1$ es $$ 1 + \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} \frac{1}{2^i \cdot i!} \prod_{k=0}^{i-1} \binom{n-2k}{2}. $$

¿Se ve bien? Me parece una respuesta bastante fea, así que tengo mis dudas. Cualquier aportación será bienvenida.

Answer 1

Según me enseñaron, hay $$ \frac{n(n-1)}{2} $$ 2 ciclos, $$ \frac{n(n-1)(n-2)(n-3)}{2^2 \cdot 2} $$ productos de dos ciclos disjuntos de 2, y en general $$ \frac{n(n-1) \cdot \dots \cdot (n-2k+2)(n - 2 k +1)}{2^k \cdot k!} $$ productos de $k$ 2 ciclos disjuntos, siempre que $2 k \le n$ .

Answer 2

Estas permutaciones se denominan involuciones . La función de recuento de involuciones en $n$ está documentado en la OEIS ici . Allí podrá encontrar fórmulas explícitas, relaciones de recurrencia, asintótica y funciones generadoras, junto con algunas referencias. OEIS (Online Encyclopedia of Integer Sequences) es un recurso bastante bueno en general para encontrar lo que se sabe sobre varios enteros, especialmente si puedes calcular los primeros términos a buscar.