Permutación cíclica

tipo de permutación
(Redirigido desde «Ciclo (permutacion)»)

Una permutación cíclica (o ciclo) es un tipo especial de permutación que fija cierto número de elementos (quizás ninguno) mientras que mueve cíclicamente el resto. En caso de no fijar ningún elemento lo denominaríamos permutación circular.

Un ciclo que deja fijos a los elementos 2 y 5 y mueve cíclicamente al resto.

Más concretamente, si un ciclo afecta a un elemento x cualquiera del conjunto, al aplicar dicho ciclo reiteradamente todos los elementos afectados por el reordenamiento pasarán por la posición de x en algún momento. Y de forma recíproca, el elemento x pasará por todas las posiciones de todos los elementos afectados por la permutación.

Los ciclos son tipos de permutación especialmente importantes, pues pueden usarse como piezas básicas para construir cualquier otra permutación.

Definición formal

editar

Sea   y  . Un ciclo de longitud   o r-ciclo de   es una permutación   tal que del conjunto   hay   elementos diferentes secuenciados,  , para los cuales se cumple que:

 , de tal manera que   si  .
  y  .

Ejemplos

editar
 
Ejemplo de un ciclo
  • La permutación   es un ciclo que no fija ningún elemento. Por ello, también se dice que es una permutación circular.
 
 
Ejemplo de una permutación formada por dos ciclos
  • La permutación   no es un ciclo, ya que es una permutación compuesta por dos ciclos.
 
De hecho, se demuestra que cualquier permutación puede descomponerse como producto de ciclos disjuntos.[1]
  • Transposición: es un ciclo de longitud 2, es decir, un 2-ciclo.

Demostración práctica

editar

Supongamos una reunión de n personas que se sientan en torno a una mesa circular con n sillas, una silla para cada persona, ¿De cuántas formas diferentes se pueden distribuir las personas en los asientos disponibles teniendo en cuenta que la mesa es circular? Para ello se requiere que los asientos sean indistinguibles, es decir, si solo se sentase una persona no importa en cual de ellos se siente pues una circunferencia no tiene principio ni final, solo se le asigna un punto arbitrario como referencia. Los objetos a colocar deben ser distinguibles o en su caso de multiconjuntos distinguibles de elementos indistinguibles, ejemplo el conjunto   = {1, 1, 1} El orden importa, pues no es lo mismo que una persona se siente a la derecha o a la izquierda de otra.

Teniendo esto en cuenta se toma la primera n-persona como punto de referencia sentándola en una silla cualquiera de la mesa, después de esto se coloca la siguiente n - 1 persona en otra n-1 silla de las disponibles, se repite el mismo proceso para la (n-2), (n-3) ... (n-n) personas con lo cual al final al aplicar la propiedad multiplicativa obtenemos que las permutaciones cíclicas de n elementos son

  formas diferentes.

Ejemplos prácticos

editar
   Dadas 5 personas en torno a una mesa redonda, ¿De cuántas formas distintas podemos sentarlas?

En este caso estamos ante una permutación circular sin restricción ni condición alguna, para ello procedemos a asignar a un elemento una posición concreta de la mesa para tomarlo como punto de referencia y permutamos a los restantes en torno a él, esto nos deja con   formas distintas pues lo que se debe permutar son los demás elementos del conjunto.

   Dadas 5 personas (Sean llamadas S,T,U,V,W) en torno a una mesa redonda tal que la persona S y T sean pareja y quieran sentarse siempre juntas, ¿De cuántas formas distintas podemos sentarlas?

En este caso tenemos 4 elementos dentro del conjunto, 3 personas sean U, V y W y otras dos que forman un multiconjunto   tomamos una de ellas como punto de referencia y permutamos al resto alrededor de ella para obtener las posibles combinaciones, en este caso tenemos un total de   formas distintas

Pero ahí no acaba el ejercicio pues hay que recordar que el multiconjunto (S,T) también puede ordenarse pues no es lo mismo que T vaya a la izquierda de S que a la derecha, esto nos da 2 formas totales de ordenarlos. Para resolver el ejercicio hay que aplicar el principio de la multiplicación, no el de la adición, pues S y T también deben sentarse a la vez que el resto de personas, no son un grupo separado que puede o no sentarse en la mesa por tanto el resultado final del ejercicio sería:

6*2 = 12 formas de sentar a 5 personas tal que 2 de ellas formen una pareja.


Por tanto a la hora de aplicar permutaciones cíclicas, hay que definir en torno a que elementos se van a permutar el resto de elementos pues si no se trataría de una permutación sin punto de referencia o permutación genérica. La conclusión es que dadas n personas, la permutación cíclica necesita al menos 1 elemento de referencia a permutar por lo tanto la fórmula estándar final queda:

 

Ejemplo concreto

editar

Tomemos una mesa de 4 personas, S,T,U,V


primero fijamos la persona S y permutamos en un ciclo las otras 3:

Obtenemos:

Fijando S.   El cardinal de  


Tomamos la persona T y permutamos de nuevo obteniendo 2 nuevas permutaciones diferentes:

Fijando T.   El cardinal de  


Tomamos la persona U y permutamos de nuevo obteniendo una última permutación no repetida:

Fijando U.   El cardinal de  


La suma de los cardinales es igual a 6, resultado de la permutación de  

Breve explicación

editar

Si tratásemos de fijar la última persona, V, y permutáramos el resto de elementos, obtendríamos una permutación cíclica ya presente, pues en las permutaciones cíclicas

 

Ya que en las permutaciones cíclicas o circulares los elementos de los "extremos" están relacionados, es decir, en el primer ejemplo a la derecha del 0 se va al 1 y en el segundo ejemplo a derecha del 0 también se va al 1 pues es un mismo ciclo.

Para entender esto, hay que destacar que en una permutación cíclica no existen primer y último elemento, tampoco se distinguen a los elementos en función de su posición de colocación sino respecto a como se encuentra su estado de permutación respecto al resto de elementos, imagínese que el conjunto   el 1 tiene a su izquierda el 5 y a su derecha el 2, el 2 por su parte tiene a su izquierda el 1 y el 3 a su derecha y así sucesivamente por tanto todas las permutaciones   son en realidad la misma pues todos los elementos ocupan la misma posición respecto al resto de elementos.

Propiedades

editar

Notación: Si un elemento   de un conjunto   se ve 'afectado' por un ciclo   entonces decimos que  .

  • Sea   un ciclo de longitud  , entonces
Si   entonces se puede escribir como
 
y   es el mínimo natural  .
  • Sea   un ciclo de longitud  , entonces
  y además   es el mínimo natural  .
De ésta proposición se deduce directamente el segundo enunciado de la proposición 1.
  • Sea   un ciclo de longitud  , entonces
 

Para calcular el número de permutaciones en una permutación circular se fija arbitrariamente un elemento como el primero y se permuta los restantes, obteniéndose:

 

Véase también

editar

Referencias

editar
  1. Birkhoff & MacLane, A survey of modern algebra, McMillan Publishing, 1977. ISBN 0-02-310070-2

Enlaces externos

editar

Página web (Matemovil: Vídeo): Explicación breve y ejercicios sobre diferentes permutaciones circulares.

Página web (Superprof): Breve explicación y unos ejercicios resueltos.

Blogspot (matematicasn): Explicación más detallada con ejercicios y vídeo.

linkfang: Explicación sobre las permutaciones cíclicas y algunas propiedades