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.

Definición 2.36. Una permutación de es una biyección de sobre sí mismo. Representaremos por al conjunto de todas las permutaciones de .

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

Proposición 2.37. .
Demostración: PENDIENTE.

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).

Definición 2.38. Llamaremos grupo simétrico sobre símbolos a equipado con la operación del producto de permutaciones.

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:

PIC

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.

Definición 2.39. Decimos que dos permutaciones y son disjuntas si éstas no mueven los mismos números. Con más precisión, lo son si implica y implica

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

Proposición 2.40. Si son disjuntas, entonces .
Demostración: Sean permutaciones disjuntas. Se debe probar que para todo . Para esto, observamos que si mueve a , con , entonces también ha de mover a por la inyectividad de , luego fija tanto a como a , lo que implica que . De forma similar se verifica que si fija a , entonces . Esto demuestra que .

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:

1σ4σ

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

2375

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

6

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.

Definición 2.41. Decimos que una permutación es un ciclo de longitud , o que es un -ciclo, si, para para ciertos , ésta verifica y cuando . Usaremos la notación    para representar al -ciclo que cumple dichas condiciones. A los 2-ciclos los llamamos transposiciones. Se trata de permutaciones que intercambian dos números y dejan fijos a todos los demás. Los ciclos de longitud 1 no mueven ningún elemento, así que todos ellos son la permutación identidad.

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 .

Proposición 2.42. Toda permutación es un ciclo o un producto de ciclos.
Demostración: Lo probaremos por inducción sobre el número de elementos movidos por una permutación . Si , el teorema es cierto, pues en ese caso . Supongamos el teorema cierto para todo entero menor que . Entonces mueve al menos un elemento, digamos . Puesto que , las potencias no pueden ser todas distintas, así que existen enteros , con , tales que , o sea, que , luego existe el menor entero tal que , o sea que existen a lo sumo potencias distintas de . Más aún, las potencias son todas distintas, pues si dos de ellas fuesen iguales, digamos con entonces con , en contradicción con la minimalidad de . Sea el ciclo Si , entonces y el teorema se cumple. Si , entonces sea el conjunto de puntos fijados por , y definamos por Entonces , donde mueve a lo sumo elementos, así que, por hipótesis de inducción, es un producto de ciclos, luego es también un producto de ciclos.

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.

Proposición 2.43. Toda permutación se descompone de forma única, salvo el orden de los factores, en un producto de ciclos disjuntos.
Demostración: Sean y dos descomposiciones de en ciclos disjuntos. Sin pérdida de generalidad, supondremos que y probaremos la proposición por inducción sobre . El caso es obvio. Supongamos la conclusión cierta para un entero y sean y dos descomposiciones de . Si mueve , entonces un y un mueven a . Puesto que los ciclos disjuntos conmutan, podemos asumir que se trata de y de . Observemos que entonces para todo , por lo que , o sea que . Por hipótesis de inducción, ambos miembros consisten de los mismos ciclos, de donde se sigue el resultado deseado.

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 .

Ejemplo 2.44. Si     , entonces     .

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 .

Ejemplo 2.45. ¿Cuántas permutaciones hay con estructura de ciclos     en ? Aplicando la fórmula (2.2), determinamos que hay ciclos de longitud 3. Obtenido este ciclo, no nos quedan más que 2 elementos para formar el 2-ciclo siguiente, luego éste sólo puede completarse de una manera y por tanto existen 20 permutaciones que son producto de un 3-ciclo y un 2-ciclo.

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.

Ejemplo 2.46. Sean      y     . Para calcular el producto , podemos empezar por rastrear a dónde va a parar el primer número que veamos en la descomposición de , que es la primera en actuar por tratarse de una composición de aplicaciones. Haciéndolo así, vemos que envía el 1 al 5 y que luego envía el 5 al 2, por lo que nuestro producto comienza por “ ”. Aplicando este mismo proceso ahora al 2, obtenemos “  ”, y continuando de esta manera con cada número que vayamos obteniendo, llegamos al resultado       .
Definición 2.47. Si y son dos permutaciones, a la permutación la llamamos conjugada de por , y la representamos por .

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:

Proposición 2.48. Sean . Si se expresa como un producto de ciclos disjuntos, entonces y tiene la misma estructura de ciclos. Con más detalle, la descomposición en ciclos disjuntos de se obtiene sustituyendo cada índice por en cada uno de los ciclos de la descomposición de .
Demostración: Es fácil ver que la conjugada de un producto de permutaciones es el producto de las conjugadas de éstas, luego basta con demostrar el teorema para el caso particular de un solo ciclo     . Sea      Hay que demostrar que . Para esto, observemos que si , entonces , pues , así que y dejan fijos a los mismos elementos. Por otra parte, si , entonces si si  o sea que , así que y coinciden en todo punto y por lo tanto son iguales.

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

(  4  7  3  )  (  5  2  ) (  1  6  )

(  4  3  1  )  (  6  7  ) (  2  5  )

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.

Teorema 2.49. Dos permutaciones y tienen la misma estructura de ciclos si y sólo si existe una permutación tal que .
Demostración: () Sean de la misma estructura de ciclos. Entonces, a cada ciclo      en la descomposición de corresponde un ciclo      en la descomposición de , y podemos definir la aplicación por para cada ciclo de estas descomposiciones. Es evidente que se trata de una permutación de , y la teorema 2.48 nos dice que .

La afirmación recíproca es la teorema 2.48.

Definición 2.50. Definimos la aplicación , llamada signatura de una permutación de , por para toda .
Proposición 2.51. Si , entonces
Demostración: Sean . Entonces

El hecho siguiente es inmediato:

Proposición 2.52. Si es una transposición, entonces .

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.

Teorema 2.53. Toda permutación se descompone en un producto de transposiciones, y los números de transposiciones de dos descomposiciones de una misma permutación tienen la misma paridad.
Demostración: Para la primera afirmación del teorema, basta probar que es cierta para un ciclo. En efecto, pues          Para la segunda afirmación, observamos que si y son dos factorizaciones de una permutación , entonces las proposiciones 2.52 y 2.51 nos dicen que por lo que y son ambos pares o ambos impares.