Permutación

Por ejemplo, escritas como tuplas, hay seis permutaciones del conjunto {1, 2, 3}, a saber (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) y (3, 2, 1).

En el caso de un elemento (1) solo hay una posible permutación:

En la definición de permutación, no se establece condición alguna sobre X, el cual puede incluso ser infinito.

Sin embargo, es común considerar únicamente el caso en que X es un conjunto finito al estudiar permutaciones.

Así un problema combinatorio consiste usualmente en establecer una regla sobre cómo deben ser las agrupaciones y determinar cuántas existen que cumplan dicha regla.

Básicamente, tres asuntos: permutaciones, combinaciones y variaciones.

Un tipo importante de esas agrupaciones son las llamadas permutaciones.

formas de ordenar el conjunto, justamente lo que enunciamos anteriormente.

Ejemplo: sea el conjunto A={1,2,3} en este caso hay 6 permutaciones, en forma compacta: 123, 132, 213, 231, 312, 321.

En álgebra, para estudiar los grupos simétricos se presentan entre paréntesis y en dos filas, en la primera siempre aparece 1 2 3.

Otro ejemplo de lo mismo: si se va a formar un comité que involucra presidente, tesorero y secretario, habiendo tres candidatos a, b, c ; cuando se elige por sorteo los cargos sucesivamente, hay seis posibilidades u ordenaciones: abc, acb, bac, bca, cab, cba.

, aunque no es la más compacta, consiste en escribirla en forma de matriz de dos filas, situando en la primera los elementos ordenados del dominio 1, 2, 3,...,n, y en la segunda fila las imágenes correspondientes a los elementos reordenados

sobre éste mediante una matriz de correspondencias: Por ser biyectiva por definición, podemos encontrar una aplicación inversa

de forma que su composición genera la aplicación identidad.

Para ello, en primer lugar intercambiamos las filas y finalmente reordenamos las columnas de modo que los elementos del dominio queden ordenados de forma natural: Existe otra notación más compacta, llamada notación de ciclos.

Un ciclo es una permutación que intercambia cíclicamente elementos y fija los restantes.

Esta notación revela mejor la estructura interna de la permutación.

Así la permutación (1 3)(2)(4 5) se escribe simplemente como (3 1)(5 4) en forma canónica.

Sergey Kitaev también usa el término «forma estándar» pero invierte los criterios: en cada ciclo se lista primero el elemento más pequeño y luego los ciclos se ordenan de mayor a menor según el primer elemento[6]​.

Por ejemplo, usando los criterios de Miklós Bóna, en una forma canónica que haya «perdido» los paréntesis, como 3 1 2 5 4 6, el primer ciclo estará formado por el primer elemento de la lista, 3, y los siguientes que sean menores que él: (3 1 2).

Una transposición es una permutación que intercambia dos elementos y fija los restantes.

Las transposiciones permiten descomponer una permutación cualquiera de una forma diferente a la descomposición en ciclos.

Nótese la diferencia entre permutación, ciclo y transposición, dado lo similar de la notación, la expresión anterior es equivalente a: La composición señalada como:

se opera de derecha a izquierda y no es conmutativa.

Dada una permutación cualquiera, se define el siguiente homomorfismo de grupos:

es el grupo simétrico de n elementos y m es un número entero, tal que existen transposiciones

impar) a la que se escribe como composición de un número par (resp.

En general, se demuestra que la mitad de las n!

Esto surge como consecuencia directa de la existencia del morfismo

que tiene como núcleo justamente a las permutaciones pares.