Permutación

Sea $X$ un conjunto finito de $n$ elementos. Una permutación de $X$ es una biyección $\sigma :X\to X$. El conjunto de todas las permutaciones de $X$ se denota por $S_n$, conocido como el Grupo simétrico de grado $n$.

$$\sigma \in S_n⟺\sigma :X\to X\text{ es biyectiva}$$

Ejemplo

Sea $X=\{1,2,3\}$. Entonces una permutación posible es:

$$\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$$

Propiedades

• La composición de dos permutaciones es otra permutación.
• Toda permutación tiene una permutación inversa: ${\sigma }^{-1}\in S_n$.
• $S_n$ es un grupo bajo la composición de funciones.
• El número total de permutaciones de $n$ elementos es $n!$

Notación

Las permutaciones usualmente se representan como

• Forma de dos líneas:

$$\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$$

• Forma cíclica: $\sigma =(132)$.

Amas indican que $1\mapsto 3$, $3\mapsto 2$, y $2\mapsto 1$.

Resultados

• Toda permutación $\sigma \in S_n$ puede expresarse como producto de transposiciones (ciclos de longitud 2).

matematicas-discretas