Algunas permutaciones dejan invariantes unos elementos, y a otros los van transformando cíclicamente hasta volver al primero. Así, la permutación (1,3,4,2,5,6) deja invariantes 1, 5 y 6, mientras 3 se transforma en 4, este en 2 y el 2 tiene como imagen el 3. A este tipo de permutaciones las llamaremos ciclos. Omitimos definiciones formales, porque aquí nuestro interés es práctico y de aprendizaje de las hojas de cálculo.
Llamaremos ciclo a una permutación que deja invariantes algunos elementos y somete a una rotaciones completas a los restantes.
Representaremos un ciclo mediante los elementos que se van transformando uno en otro, omitiendo los invariantes. Así, (3,4,2) representaría a la anterior permutación. Podemos someter a los elementos 3,4,2 a una rotación en el orden y representarían el mismo ciclo: (3,4,2) = (4,2,3) = (2,3,4), pero otro tipo de alteración del orden, como (3,2,4) ya representaría un ciclo distinto. Si aplicamos reiteradamente un ciclo, cada elemento irá pasando por todas las posiciones posibles e, inversamente, por una posición dada irán pasando ordenadamente todos los elementos.
Un mismo ciclo se puede representar comenzando con cualquiera de sus elementos si se respeta el orden circular.
Un ciclo de un elemento representa un elemento invariante, y el de dos, una transposición entre dos elementos. Si el ciclo abarca la permutación completa, a esta la llamaremos cíclica.
La propiedad más importante de los ciclos es que toda permutación se puede descomponer en ciclos disjuntos de forma única salvo el orden. Según esto, la del ejemplo podemos representarla como (1,3,4,2,5,6)=(3,4,2)(1)(5)(6). Se suelen ordenar los ciclos por su magnitud, de mayor a menor.
¿Cómo descomponer una permutación en ciclos?
El procedimiento puede ser el siguiente:
Elegimos el elemento 1, y aplicamos la permutación de forma reiterada hasta que la imagen vuelva a ser 1. Como el conjunto es finito, esto se acabará logrando, con lo que ya tendremos el primer ciclo de la descomposición. Buscamos después el siguiente elemento que no pertenezca al ciclo conseguido (si hemos acabado es que la permutación estudiada se reduce a un solo ciclo, es cíclica) y efectuamos la misma operación para obtener el segundo ciclo, y así sucesivamente hasta agotar el conjunto.
Por ejemplo, la permutación (4, 2, 6, 7, 8, 9, 10, 11, 3, 1, 5) nos llevaría al siguiente proceso:
Comenzamos con el 1. Las sucesivas imágenes serían: 1 – 4 – 7 – 10 – 1. Ya tendríamos el primer ciclo (4, 7, 10, 1).
Buscamos el siguiente elemento no estudiado aún: el 2, que se transforma en sí mismo. El siguiente ciclo es, pues, (2)
Siguiente elemento libre: 3, que engendra: 3 – 6 – 9 – 3, formando el ciclo (3, 6, 9)
Por último, con 5 logramos (5, 8, 11)
Hemos terminado: (4, 2, 6, 7, 8, 9, 10, 11, 3, 1, 5) = (4, 7, 10,1) (3, 6, 9) (5, 8, 11) (2)
Como cada ciclo opera sobre elementos disjuntos, esta descomposición es un producto en Sn (ver entrada anterior del blog), en el que los ciclos son permutables y por tanto, no influye el orden.
En este proceso los ciclos que se formen serán disjuntos, pues si dos de ellos tuvieran un elemento común, al aplicar el ciclo sobre él reiteradamente se incluirían todos los elementos, y los ciclos serían en realidad uno solo.
El número de ciclos en que se descompone una permutación varía entre 1, si ella misma es cíclica, hasta n, si se trata de la permutación identidad.
Podemos conseguir que una hoja de cálculo haga lo mismo:
Lo hemos implementado en Excel y Apache OpenOffice (http://hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#ciclos)
Observa que ha creado una fila en la que va tomando nota de los ciclos a los que pertenece cada elemento, y después ha escrito debajo la composición de cada ciclo. Es una tarea un poco larga, por lo que sólo explicaremos los fundamentos, remitiendo después a la hoja ya confeccionada.
Proceso para encontrar los ciclos:
1) Se crean unas memorias que contendrán la información de los ciclos que se van ocupando. Al principio se inician todas a cero.
2) En cada paso del proceso se busca el primer elemento cuyo número de ciclo es 0. Se aumenta en una unidad el número del ciclo, que, por tanto, comenzará en 1. Con un procedimiento similar al usado en la anterior entrada, se aplica reiteradamente la permutación hasta completar el ciclo.
Este paso se da mientras exista un elemento con número de ciclo 0. Para cada elemento, se irá escribiendo en la hoja a qué ciclo pertenece.
3) Localizados los ciclos, se van buscando los elementos de cada uno y se escriben en filas distintas debajo del esquema. Esta parte es más informática que matemática, y la podemos omitir.
Generación aleatoria
Como la hoja de cálculo ofrecida no tiene más objetivo que el de explicar el concepto, se ha añadido la posibilidad de generar aleatoriamente una permutación para comprender mejor la descomposición en ciclos.
Orden de un ciclo
No es difícil entender que el orden de un ciclo es su longitud, ya que los elementos invariantes seguirán siéndolo aunque reiteremos y los cíclicos se irán recorriendo uno por uno y se llegará al primero cuando se recorra toda la longitud:
El orden de un ciclo coincide con su longitud
También es sencillo entender que si una permutación se descompone en ciclos, su orden será el MCM de las longitudes de los mismos.
Así, el orden de (1)(2, 3, 7)(4, 5)(6) será 6, el mcm(1, 3, 2, 1)
En la misma hoja se puede estudiar el orden de los ciclos y el de la permutación total
El orden de los ciclos aparece en la parte izquierda de los mismos
El orden total, MCM de los de los ciclos lo tendrás en la parte derecha
Llamaremos transposición a un ciclo de orden 2. Todo ciclo, y en consecuencia toda permutación, se puede descomponer en transposiciones. Se comprende sólo con estudiar este desarrollo:
(a, b, c, d, e)=(a, e)(a, d)(a, c)(a, b)
Esta descomposición no es única.
Algunos cálculos
Permutaciones circulares o cíclicas
Puede ocurrir que una permutación sea en sí misma un ciclo. La llamaremos cíclica o circular. Dentro del grupo simétrico Sn el número de permutaciones cíclicas equivale a (n-1)! Es algo muy conocido y se justifica porque para inventarte una permutación de este tipo en primer lugar has de ordenar todos los elementos, lo que puedes realizar de n! formas diferentes y una vez elegida una, esta representa n circulares idénticas, porque tienes n formas de elegir el primer elemento, luego el número es n!/n=(n-1)!
Permutaciones de n elementos que son ciclos de orden k
Deberemos elegir k elementos para el ciclo y dejar los restantes n-k fijos. El elegirlos nos supone Cn,k formas y dentro de los elegidos, (k-1)! ciclos posibles, luego el número total de ciclos de orden k será
Permutaciones reducidas
Son aquellas que no dejan fijo ningún elemento, las que en la descomposición en ciclos ninguno de ellos tiene orden 1. Son las conocidas como desarreglos (o desbarajustes) Los puedes estudiar en http://hojamat.es/sindecimales/combinatoria/teoria/teorcomb.pdf
En esa dirección hemos explicado su fórmula
No hay comentarios:
Publicar un comentario