Índice
DESCRIPTION
indice para que guiesTRANSCRIPT
Índice
2.Ciclos
2.1 Definición formal
2.2 Ejemplos
2.3 Propiedades
2. CICLOS
Un 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 cíclica.
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 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
La permutación es un ciclo que no fija ningún elemento. Por ello, también se dice que es una permutación cíclica.
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.
Propiedades
Notación: Si un elemento de un conjunto se
ve 'afectado' por un ciclo entonces
decimos que .
Sea un ciclo de longitud , entoncesSi 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