2.3 Permutaciones

Antes de continuar, es conveniente contar con un concepto que nos permitirá dar ejemplos concretos de muchos de los conceptos que vienen a continuación.

En matemáticas elementales, una permutación de una lista de objetos se entiende como un reordenamiento de los elementos de la lista. Por ejemplo, para la lista tenemos los ordenamientos siguientes: Observemos que cualquiera de estos reordenamientos de puede entenderse como una biyección del conjunto en sí mismo. Por ejemplo, el reordenamiento de es la aplicación que envía el 1 al 3, el 2 al 4, el 3 al 2 y el 4 al 1. En general, y puesto que ningún reordenamiento introduce repeticiones ni omisiones de los elementos de , deducimos que, en efecto, todo reordenamiento queda caracterizado por una biyección de en sí mismo.

Notemos que la definición anterior es en esencia la misma si en lugar del conjunto consideremos cualquier otro conjunto de elementos. Teniendo el mismo cardinal que , podemos pensar que no es más que con sus elementos “renombrados”. Para expresar esta situación con más detalle, supongamos que es el conjunto de las permutaciones de elementos de , es decir, el conjunto de biyecciones . Al ser , existe una biyección que “traduce” los elementos de a elementos de , y con ella podemos traducir toda permutación en una permutación de elementos de (la composición de biyecciones es una biyección). Está claro que queda unívocamente determinada por y , o sea, que la aplicación dada por es una biyección entre las permutaciones de y las permutaciones de , luego los conjuntos y son en efecto intercambiables. Por lo tanto, cuando en algún punto hablemos del conjunto de las permutaciones en un conjunto de elementos, el lector tendrá claro que no se trata de ningún concepto nuevo y que todo lo dicho para vale igual para este conjunto.

Como posiblemente el lector ya los sepa, existen formas distintas de ordenar un conjunto de elementos, o sea que

Puesto que hemos definido a las permutaciones compo biyecciones de un conjunto en si mismo, ahora podemos entender el proceso de reordenar dos veces un conjunto de objetos simplemente como la composición de dos permutaciones: si , es la permutación que resulta de aplicar seguida de , pues ya sabemos (proposición xxx) que la composición de biyecciones es de nuevo una biyección, o sea, que dicha composición es una operación binaria en , a la cual nos referiremos como producto de permutaciones. Se deja al lector verificar que esta operación verifica las propiedades de la definición de grupo (teorema 2.18).

Por lo regular representaremos el producto de dos permutaciones y (en ese orden) con la notación en lugar de .

A continuación estudiaremos algunas propiedades básicas de las permutaciones que nos permitirán trabajar con ellas de manera más eficiente.

Una notación común para especificar una permutación consiste en un arreglo de dos filas como formada por columnas en las que se coloca cada encima del valor al que éste es enviado por . Por ejemplo, si es la permutación de dada por entonces Aunque esta notación es un tanto tediosa, tiene la ventaja de facilitar el cálculo de productos de permutaciones. Por ejemplo, si es como arriba y tenemos que donde el cálculo se realiza siguiendo los números de derecha izquierda (en la notación , actúa después de ), como se ilustra en la imagen siguiente:

La verdad es que esta forma de representar permutaciones no nos interesa mucho, pues vamos a introducir otra notación que no sólo es más concisa, sino que además hace manifiestas algunas propiedades importantes de una permutación dada y también permite hacer cálculos más rápidos con permutaciones. Esta notación se apoya en algunos conceptos adicionales que introducimos a continuación.

Aunque la composición de aplicaciones no es conmutativo, sí lo es entre permutaciones disjuntas.

Consideremos ahora la permutación y el efecto que tiene aplicar repetidamente a los elementos de . Cuando aplicamos por primera vez, ésta envía el 1 al 4. Como vuelva a actuar, ésta envía el 4 de regreso al 1, dando como resultado el “ciclo” de la imagen siguiente:

Ahora vemos qué pasa con los demás elementos. El menor de los enteros de que no figura en el ciclo de arriba es el 2. Cuando actúa sobre el 2, éste es enviado al . Si actúa de nuevo, el 3 es enviado al 7, y si actúa otra vez, el 7 es enviado al 5. Al actuar sobre el 5, éste es enviado al 2, completándose así el ciclo

El menor (y el único) de los enteros del conjunto que no está en el ciclo anterior es el 6, que queda fijado por y por tanto su ciclo es

La situación descrita por estos tres diagramas puede expresarse con la notación      que especifica el efecto que tiene sobre cada elemento de . Decimos entonces que hemos descompuesto en “producto de ciclos disjuntos”. Si a los ciclos los definimos como ciertas permutaciones especiales, podemos dar completo sentido literal esas palabras.

Observemos que la notación para un -ciclo no es única, pues “rotar” las posiciones de sus números da lugar a la misma permutación. Por ejemplo               o sea que hay formas distintas de escribir el mismo -ciclo. Puesto que existen -tuplas ordenadas de elementos tomados de , el total de -ciclos distintos en es (2.2)

Por otra parte, cualquier ciclo de longitud uno es simplemente la identidad en , que comúnmente representaremos por .

El procedimiento con el que más arriba factorizamos      es de carácter general y puede usarse para factorizar cualquier permutación . El resultado es siempre un producto de ciclos disjuntos, como lo establece el teorema siguiente.

Es inmediato que el inverso del ciclo      es el ciclo      Si la descomposición en ciclos disjuntos de es , entonces pues ciclos disjuntos conmutan. Así, calcular la inversa de consiste simplemente en invertir el orden de los elementos de cada ciclo en la descomposición de .

Nos referiremos como la estructura de ciclos de una permutación al número de -ciclos que aparecen en la descomposición de en ciclos disjuntos para cada .

En la factorización de una permutación en ciclos disjuntos, por lo regular omitimos los ciclos de longitud 1 que resultan de considerar los elementos fijados por , ya que dichos ciclos son todos la permutación identidad y resulta redundante escribirlos. Sin embargo, en ocasiones sí resulta útil incluirlos. Cuando incluimos un 1-ciclo para cada número fijado por , hablamos de una factorización completa de en producto de ciclos disjuntos.

Consideremos las permutaciones      y     . Al calcular                  observamos que y tienen la misma estructura de ciclos, y que, además, Se trata de una regla general:

Propongámonos ahora determinar si existe alguna relación entre dos permutaciones que tengan la misma estructura de ciclos. Consideremos, por ejemplo, las permutaciones      y      de , y definamos por

Puesto que estamos considerando factorizaciones completas de y en ciclos disjuntos, está bien definida y es biyectiva, luego     . Tenemos entonces que      donde la última igualdad se da por la teorema 2.48. Ahora demostraremos esta relación en el caso general.

El hecho siguiente es inmediato:

Es posible descomponer una permutación en un producto de transposiciones, si bien no de forma única. Sin embargo, el teorema siguiente nos dice que el número de factores en una descomposición así es único módulo dos.