Permutación

En matemáticas, unha permutación é a variación da orde ou da disposición dos elementos dun conxunto.

Por exemplo, no conxunto {1,2,3}, cada ordenación posible dos seus elementos, sen repetilos, é unha permutación. Existen un total de 6 permutacións para estes elementos: "1,2,3", "1,3,2", "2,1,3", "2,3,1", "3,1,2" e "3,2,1".

 Definición formal 
A definición intuitiva de permutación, como ordenamentos dos elementos dun conxunto formalízase co uso da linguaxe de funcións matemáticas.

miniatura|Exemplo de permutación considerada como función bixectiva.
Para ilustrar a definición, retomemos o exemplo descrito na introdución. No exemplo, X={1, 2, 3}.

Entón, cada correspondencia un a un entre o conxunto {1, 2, 3} nel mesmo equivale a unha forma de ordenar os elementos.

Por exemplo, a asignación bixectiva dada por
 1 → 1
 2 → 2
 3 → 3
pode facerse corresponder coa ordenación "1, 2, 3".

Por outro lado, a asignación bixectiva dada por
 1 → 3
 2 → 2
 3 → 1
pode facerse corresponder coa ordenación "3, 2, 1".

Na definición de permutación, non se establece condición algunha sobre X, o que pode incluso ser infinito. Porén, é común considerar unicamente o caso en que X é un conxunto finito ao estudar permutacións.

 En combinatoria 
A combinatoria trata do número de diferentes maneiras que existen de considerar conxuntos formados a partir de elementos dun conxunto dado, respectando certas regras, como o tamaño, a orde, a repetición, a partición. Así, un problema combinatorio consiste usualmente en establecer unha regra sobre como deben ser as agrupacións e determinar cantas existen que cumpran esa regra. Basicamente, tres tipos: permutacións, combinacións e variacións (aínda que se poden considerar as permutacións como un tipo especial de variacións), todas sen repetición ou con ela.

Un tipo importante desas agrupacións son as chamadas permutacións. Dada unha n-upla ordenada de elementos dun conxunto, o número de permutacións é o número de n-uplas ordenadas .

 Fórmula do número de permutacións 
Dado un conxunto finito   de  elementos, o número de todas as permutacións é igual a  factorial de n:
.

Demostración:
Dado que hai  formas de escoller o primeiro elemento e, unha vez escollido este, só temos  formas de escoller o segundo elemento, e así sucesivamente, vemos que cando chegamos ao elemento k-ésimo só temos  posibles elementos para escoller, o que nos leva a que temos  formas de ordenar o conxunto, xustamente o que enunciamos anteriormente..

Exemplo: sexa o conxunto A={1,2,3} neste caso hai 6 permutacións, en forma compacta: 123, 132, 213, 231, 312, 321. En álxebra, para estudar os grupos simétricos preséntanse entre parénteses e en dúas filas, na primeira sempre con 1 2 3.

 En teoría de grupos 
 Notacións 
miniatura|Representación gráfica da permutación σ que revela a súa estrutura composta por 2 ciclos de lonxitude 4.
A primeira forma de escribir unha permutación σ, aínda que non é a máis compacta, consiste en escribila en forma de matriz de dúas filas, situando na primeira fila os elementos do dominio 1, 2, 3,..., n, e na segunda as imaxes correspondentes aos elementos reordenados σ(1), σ(2), σ(3),...,σ(n).

Por exemplo, dado o conxunto ordenado  podemos expresar unha permutación  sobre este mediante unha matriz de correspondencias:

Claramente é bixectiva, xa que podemos atopar unha aplicación inversa  de forma que a súa composición xera a aplicación identidade. Para iso, en primeiro lugar intercambiamos as filas e finalmente reordenamos as columnas de modo que os elementos do dominio queden ordenados de forma natural:

 Notación de ciclos 
Existe outra notación máis compacta, chamada notación de ciclos. Un ciclo é unha permutación que intercambia ciclicamente  elementos e fixa os restantes.

Esta notación revela mellor a estrutura interna da permutación. Para iso:
 Empezamos con calquera elemento. Escribímolo e á súa dereita escribimos a súa imaxe, á dereita desta, a imaxe da súa imaxe, e seguimos así ata que se complete un ciclo.
 Despois escollemos calquera elemento non contido no primeiro ciclo, volvemos escribir a súa imaxe á súa dereita, e continuamos ata completar o segundo ciclo.
 O proceso continúa ata que a permutación enteira quede descrita como produto de ciclos disxuntos.

Seguindo co mesmo exemplo, en notación de ciclos,  quedaría expresada como composición de dous ciclos:
= (1 3 5 6 )(2 4 7 8)

 Descomposición dunha permutación en ciclos disxuntos 
A descomposición realizada polo procedemento anterior non é única en principio, pois poderían obterse calquera destes resultados equivalentes:
 = (1 3 5 6)(2 4 7 8)=(2 4 7 8) (1 3 5 6)= (8 2 4 7)(6 1 3 5)

A descomposición canónica dunha permutación como produto de ciclos obtense colocando en primeiro lugar de cada ciclo o número máis pequeno do mesmo. Posteriormente continúase colocando ciclos, primeiro o que teña un primeiro elemento menor. Frecuentemente, adoitan omitirse os ciclos de lonxitude 1. Así a permutación (1 3)(2)(4 5) escríbese simplemente como (1 3)(4 5).

 Descomposición dunha permutación en transposicións 
Unha transposición é unha permutación que intercambia dous elementos e fixa os demais. Ese, doutro modo, é un ciclo de lonxitude 2. Unha propiedade interesante é que calquera permutación se pode construír como unha composición de transposicións, aínda que non de maneira única. Dadas dúas descomposicións en transposicións dunha permutación cúmprese que ambas empregarán un número par ou ambas empregarán un número impar, iso permite definir de maneira unívoca a paridade dunha permutación.

As transposicións permiten descompoñer unha permutación calquera dunha forma diferente á descomposición en ciclos. En particular, as transposicións que aparezan non terán que ser disxuntas: por exemplo, o ciclo (1 2 3 4) = (1 2) (2 3) (3 4). Aquí a orde de aplicación é importante: en primeiro lugar (3 4) deixa o 4 no seu sitio definitivo e o 3 descolocado. Despois (2 3) deixa en su sitio definitivo o 3 e o 2 descolocado, que quedará recolocado definitivamente por (1 2).

Para ver que calquera permutación se descompón como produto de transposicións basta ver que todo ciclo o fai. Porén, a descomposición non é única, por exemplo:

O número de transposicións da descomposición tampouco é único. Por exemplo:

Pero a paridade do número de transposicións da descomposición si está determinada. É dicir, para calquera par de descomposicións distintas de  con n e con m transposicións, respectivamente, n e m teñen a mesma paridade (serán simultaneamente pares ou impares).

Dada unha permutación calquera, defínese o seguinte homomorfismo de grupos:

onde  é o grupo simétrico de n elementos e m é un número enteiro, tal que existen transposicións  tales que:

 Permutación par e permutación impar 
Chámase permutación par (respectivamente, impar) á que se escribe como composición dun número par (respectivamente, impar) de transposicións.

Como exemplo, das 6=3! permutacións do conxunto {1, 2, 3}, escritas en notación de ciclos:
 (1 2), (2 3) e (1 3) son, de forma trivial, impares.
 (1 2 3) e (2 3 1) son pares, como é fácil de comprobar ao aplicar a fórmula anterior de descomposición dun ciclo en transposicións.
 e (a identidade) tamén é par.

En xeral, demóstrase que a metade das n! permutacións dun conxunto de n elementos son pares e a outra metade impares. Isto xorde como consecuencia directa da existencia do morfismo  que ten como núcleo xustamente a as permutacións pares.

 Estrutura de grupo 
Dado un número natural , consideramos o conxunto . Definimos o grupo de permutacións de  elementos, que denotaremos por , ou o que é o mesmo, o conxunto de aplicacións bixectivas de  a .

As permutacións pares forman un subgrupo normal de índice 2 do grupo Sn, ao que chamaremos grupo alternado, e notaremos por .

 Dato histórico 
O estudo das permutacións das raíces das ecuacións alxébricas permitiulle a Galois elaborar os inicios da teoría de grupos e empregar este vocábulo, por primeira vez, en matemáticas. Comezou polos grupos non abelianos.

O concepto de permutación aparece na obra hebrea Séfer Yetzirah ('O libro da creación'), un manuscrito elaborado por un místico entre o ano 200 e o 600. Pero existía xa un resultado anterior de Xenócrates de Calcedonia (396-314 a. C.)Grimaldi, Ralph: «Matemáticas discreta e combinatoria» 0-201-65376-1 , pág.44

 Notas 

 Véxase tamén 
 Outros artigos 
 Ciclo (permutación)
 Matriz permutación
 Combinatoria
 Combinacións
 Variación

Categoría:Matemática discreta