Voy a resumir todo lo que sé de permutaciones, pero no tiene nada que ver con probabilidad (que no la he estudiado aún), sino con teoría de grupos:
Una permutación es un endomorfismo de los números naturales, es decir, es una aplicación en la que a cada número natural se le asigna otro, no dejando a ninguno desemparejado y sin que se repita ninguna asignación (aplicación biyectiva). Como el conjunto de los números naturales es un conjunto ordenado, cada permutación se puede entender como una posible ordenación de los elementos.
El número de permutaciones posibles de un conjunto de
n elementos viene dado por el factorial de
n, que es
[center]
[/center]
Por convenio, 0!=1 (el número de permutaciones posibles del conjunto vacío es 1).
Por tanto, si tenemos un conjunto de tres elementos {
a,
b,
c}, entonces podemos ordenarlo de 3!=3·2·1=6 maneras diferentes: (
a,
b,
c), (
a,
c,
b), (
b,
a,
c), (
b,
c,
a), (
c,
a,
b) y (
c,
b,
a).
Si queremos tomar permutaciones de una longitud dada
m de un conjunto de
n elementos (m<n, porque si no, no tendría sentido), entonces la cantidad de permutaciones posibles es
[center]
[/center]
Hay varias formas de escribir una permutación y la más interesante es la notación de ciclos. Sea una permutación
[center]
[/center]
La fila de arriba indica el orden y la fila de abajo los elementos. Esta permutación puede escribirse también como un producto de ciclos. En este caso, el 1 lleva al 2, el 2 al 3, el 3 al 4, el 4 al 5 y el 5 al 1 (el principio). Esto es un ciclo.
[center]
[/center]
Pongamos esta otra permutación:
[center]
[/center]
El 1 lleva al 2, el 2 al 3 y el 3 al 1. Por otra parte, el 4 lleva al 5 y el 5 lleva al 4. Aquí la permutación se expresa como producto de dos ciclos disjuntos.
[center]
[/center]
El caso extremo es este, pues el cada número lleva a sí mismo y hay cinco ciclos disjuntos:
[center]
[/center]
Añadiendo la operación de composición (hacer una permutación y luego otra) las permutaciones de un conjunto de
n elementos forman una entidad matemática que se llama grupo, pues cumplen las siguientes propiedades:
- Para dos permutaciones cualesquiera, su composición es también una permutación.
- Asociatividad: para tres permutaciones, la composición de las dos primeras compuesta con la tercera es igual a la primera compuesta con la composición de las otras dos.
- Elemento identidad: existe una permutación que compuesta con cualquier otra, deja invariante a esta permutación.
- Elemento inverso: para cada permutación, existe una permutación inversa que deja el conjunto invariante.
El grupo de permutaciones de
n elementos es isomorfo (igual, en términos de propiedades) al grupo de las rotaciones de una figura con
n vértices, que traslada un vértice a otro.