Involuciones de $S_n$

Question

¿Cómo puedo encontrar cuántos involución son en $S_n$ para cualquier $n\in Z$? Digamos que para $S_4$. ¿Hay una ecuación o cualquier cosa que me permite encontrarlo con facilidad?

Answer 1

Una involución es cualquier permutación $\sigma$ tal que $\sigma^2 = id$. Por lo tanto, el número de involuciones de $S_n$ será el número de permutaciones $\sigma \in S_n$ tal que $\sigma$ orden $2$.

La idea clave es que el $\sigma \in S_n$ orden $2 \iff \sigma$ $2$ciclo o de un producto de disjuntas $2$-ciclos. Así que si $\sigma$ es un producto de $m$ $2$-ciclos, entonces no se $\displaystyle \binom{n}{2m}$ formas de elección de $2m$ elementos, y a partir de ahí $\displaystyle \frac{(2m)!}{m!2^m}$ formas de la vinculación de los elementos seleccionados juntos en discontinuo $2$-ciclos. Por supuesto, $m$ no puede exceder $\displaystyle \frac{n}{2}$. Por lo tanto, el número total de involuciones es:

$$\sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n}{2k}\frac{(2k)!}{k!2^k}$$

(La suma comienza a $k = 0$, ya que, trivialmente, la identidad es una involución)

Answer 2

Otro enfoque porque yo soy parcial a la generación de funciones: Vamos a $a_n$ denotar el número de involuciones en $S_n,$ y tenga en cuenta que $a_0 = a_1=1.$ Supongamos que queremos construir involuciones en $S_n, n\geq 2$ (de los cuales hay $a_n$). Tal involución corrige $n$ o se mueve en algún lugar. Si corrige $n$, entonces es sólo una involución en el resto de las $n-1$ elementos, y no se $a_{n-1}$ de estos. Si se mueve de $n,$, entonces es libre de moverse a cualquiera de los otros $n-1$ elementos y, a continuación, el resto de la involución es sólo una involución en el resto de las $n-2$ elementos.

Así que tenemos la relación de recurrencia $a_n = a_{n-1} + (n-1)a_{n-2}.$ Esto es bueno para un práctico de cálculo para las pequeñas $n.$

Ahora vamos a $\displaystyle A(z) = \sum_{n=0}^{\infty} a_n \frac{z^n}{n!}$ ser la Exponencial de la Generación de la Función de la secuencia. Reemplace $a_n$ $a_{n-1}+(n-1)a_{n-2}$ en esta suma y diferenciar ambos lados para obtener la ecuación de $A' = (1+z)A.$ Resolver esto da $A(z) = \exp( z + z^2/2).$

$$ A(z) = \sum_{m=0}^{\infty} \frac{ (z+z^2/2)^m }{m!}.$$

El coeficiente de $z^n$ de esta suma es $a_n/n! \ .$ vemos que los términos con $m< \lfloor n/2 \rfloor$ $m>n$ no contribuyen a la $z^n$ coeficiente.

Para $m=n-k$ $k=0,1,\ldots, \lfloor n/2 \rfloor,$ el plazo es $\dfrac{(z+z^2/2)^{n-k}}{(n-k)!}.$ sólo obtener un $z^n$ plazo si usted escoge $z$ $n-2k$ de la $n-k$ factores y $z^2/2$ el otro $k$ factores. Desde allí se $\binom{n-k}{k}$ maneras de hacer esto, el coeficiente de $z^n$ esto es $\binom{n-k}{k} \dfrac{1}{2^k (n-k)!} =\dfrac{1}{2^k k! (n-2k)!}$ .

Por lo tanto, $\displaystyle a_n = \sum_{k=0}^{ \lfloor n/2 \rfloor } \frac{n!}{2^k k! (n-2k)!}$ (que por supuesto es el mismo que lo Kaj escribió en su respuesta).

Answer 3

Sin embargo, otra manera de contar involuciones en $S_{n}$ es que el número de involuciones en $S_{n}$ $\sum_{\chi \neq 1} \chi(1),$ donde $\chi$ ejecuta a través de la no-trivial complejo irreductible personajes de $S_{n}.$ En general, para un grupo finito $G,$ el número de soluciones de $x^{2} = 1$ $G$ (que cuenta la identidad de $1_{G}$ como una solución) está dada por $\sum_{\chi} \nu(\chi)\chi(1),$ donde $\chi$ carreras más complejo irreductible personajes de $G$ $\nu(\chi)$ es el Frobenius-Schur indicador de $\chi,$ $0$ si $\chi$ no es un valor real, $-1$ si $\chi$ es un valor real, pero que no se otorgan por cualquier representación real, y $1$ si $\chi$ es dado por una representación real. En el caso de$S_{n},$ se sabe que todo el complejo irreductible carácter es dado por una representación real, por lo que el especial caso citado de la siguiente manera. Sin embargo, para un gran$n,$, mientras que es de rutina para determinar el carácter grados para$S_{n}$, en teoría, se vuelve laborioso. En el caso de que se le preguntó acerca de, $S_{4},$ la irreductible carácter grados se $1,1,2,3,3,$ hay $9$ involuciones. Para $S_{5},$ la irreductible carácter grados se $1,1,6,4,4,5,5,$ hay $25$ involuciones.