Permutación cíclica

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

Sea $n\geq 2$ y $2\leq r\leq n$ . Un ciclo de longitud $r$ o r-ciclo de $S_{n}$ es una permutación $\sigma$ tal que del conjunto $\{1,2,...,n\}$ hay $r$ elementos diferentes secuenciados, $a_{1},a_{2},...,a_{r}$ , para los cuales se cumple que:

M(\sigma )=\{a_{1},a_{2},...,a_{r}\}

, de tal manera que

\sigma (x)=x

si

x\neq a_{i}\forall i

.

\sigma (a_{1})=a_{2},\sigma (a_{2})=a_{3},...,\sigma (a_{r-1})=a_{r}

y

\sigma (a_{r})=a_{1}

.

Ejemplos

Ejemplo de un ciclo

La permutación $\sigma$ es un ciclo que no fija ningún elemento. Por ello, también se dice que es una permutación circular.

\sigma ={\begin{pmatrix}1&2&3&4&5&7&6&8\\4&5&7&6&8&1&2&3\end{pmatrix}}={\begin{pmatrix}1&4&6&2&5&8&3&7\\4&6&2&5&8&3&7&1\end{pmatrix}}

Ejemplo de una permutación formada por dos ciclos

La permutación $\omega$ no es un ciclo, ya que es una permutación compuesta por dos ciclos.

\omega ={\begin{pmatrix}1&2&3&4&5&7&6&8\\3&4&5&7&6&8&1&2\end{pmatrix}}={\begin{pmatrix}1&3&5&6\\3&5&6&1\end{pmatrix}}{\begin{pmatrix}2&4&7&8\\4&7&8&2\end{pmatrix}}

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

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 $C_{1}$ = {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

$PC_{n}=(n-1)!$ formas diferentes.

Ejemplos prácticos

   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 $PC_{5}=(5-1)!=4!=24$ 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 $(S,T)$ 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 $PC_{4}=(4-1)!=6$ 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:

$PC_{n}=(n-1)!$

Ejemplo concreto

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. $D_{S}=\{(S,T,U,V),(S,V,T,U),(S,U,V,T)\}$ El cardinal de $|D_{S}|=3$

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

Fijando T. $D_{T}=\{(T,V,S,U),(T,S,V,U)\}$ El cardinal de $|D_{T}|=2$

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

Fijando U. $D_{U}=\{(U,S,T,V)\}$ El cardinal de $|D_{U}|=1$

La suma de los cardinales es igual a 6, resultado de la permutación de $PC_{4}=(4-1)!=6$

Breve explicación

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

$\{0,1\}=\{1,0\}$

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 $C=\{1,2,3,4,5\}$ 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 $\{1,2,3,4,5\}=\{5,1,2,3,4\}=\{4,5,1,2,3\}=\{3,4,5,1,2\}=\{2,3,4,5,1\}$ son en realidad la misma pues todos los elementos ocupan la misma posición respecto al resto de elementos.

Propiedades

Notación: Si un elemento $a$ de un conjunto $A$ se ve 'afectado' por un ciclo $\sigma :A\to A$ entonces decimos que $a\in M(\sigma )$ .

Sea $\sigma$ un ciclo de longitud $r$ , entonces

Si

a\in M(\sigma )

entonces se puede escribir como

\sigma =(a,\sigma (a),...,\sigma ^{r-1}(a))

y

r

es el mínimo natural

k\geq 1:\sigma ^{k}(a)=a

.

Sea $\sigma$ un ciclo de longitud $r$ , entonces

\sigma ^{r}=Id

y además

r

es el mínimo natural

k\geq 1:\sigma ^{k}=Id

.

De ésta proposición se deduce directamente el segundo enunciado de la proposición 1.

Sea $\sigma$ un ciclo de longitud $r$ , entonces

\sigma ^{r-i}=\sigma ^{-i}

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: