Ciclo (permutación)

Ciclo (permutación)
Un ciclo que deja fijos a los elementos 2 y 5 y mueve cíclicamente al resto.

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.

Contenido

Definición formal

Sea n\geq2 y 2\leq r\leq n. Un ciclo de longitud r o r-ciclo de Sn es una permutación σ tal que del conjunto {1,2,...,n} hay r elementos diferentes secuenciados, a1,a2,...,ar, para los cuales se cumple que:

M(σ) = {a1,a2,...,ar}, de tal manera que σ(x) = x si x\neq a_i \forall i.
σ(a1) = a2,σ(a2) = a3,...,σ(ar − 1) = ar y σ(ar) = a1.

Ejemplos

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 cíclica.
\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 ω 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.

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 σ un ciclo de longitud r, entonces
Si a \in M(\sigma) entonces se puede escribir como
σ = (a,σ(a),...,σr − 1(a))
y r es el mínimo natural k\geq1 : \sigma^k(a)=a.
  • Sea σ un ciclo de longitud r, entonces
σr = Id y además r es el mínimo natural k\geq1 : \sigma^k = Id.
De ésta proposición se deduce directamente el segundo enunciado de la proposición 1.
  • Sea σ un ciclo de longitud r, entonces
σr − i = σ − i

Referencias

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

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • Permutación — Saltar a navegación, búsqueda En matemáticas, dado un conjunto finito con todos sus elementos diferentes, llamamos permutación a cada una de las posibles ordenaciones de los elementos de dicho conjunto. Por ejemplo, en el conjunto {1,2,3}, cada… …   Wikipedia Español

  • Ciclo (desambiguación) — Ciclo Serie de fases por las que pasa un fenómeno periódico hasta que se reproduce una fase anterior. una bicicleta (se usa mucho el término ciclo en los reglamentos de conducción) en literatura: Epanadiplosis o ciclo (figura retórica) Ciclo… …   Wikipedia Español

  • Problema abstracto — Saltar a navegación, búsqueda En ciencia computacional teórica, un problema abstracto o problema computacional es una relación entre un conjunto de instancias y un conjunto de soluciones. Un problema abstracto permite establecer formalmente la… …   Wikipedia Español

  • Grupo simétrico — Grafo de Cayley de un grupo simétrico de orden 4 (S4) En matemáticas, el grupo simétrico sobre un conjunto X, denotado por SX es el grupo formado por las funciones biyectivas (permutaciones) de X en sí mismo. Los subgrupos de SX se deno …   Wikipedia Español

  • Intel 80486 — 486 Microprocesador La parte inferior de un Intel 80486DX2 Producción 1989   2007 …   Wikipedia Español

  • Problema del viajante — Saltar a navegación, búsqueda Si un viajante parte de la ciudad A y las distancias a todas las demás ciudades son conocidas, ¿cuál es la ruta óptima que debe elegir para visitar todas las ciudades y volver a la ciudad de partida? Contenido …   Wikipedia Español

  • Grupo diedral — Este copo de nieve tiene la simetría diedral de un hexágono regular. En matemáticas, un grupo diedral es el grupo de simetría de un polígono regular, incluyendo tanto rotaciones y reflexiones.[1] …   Wikipedia Español

  • Quicksort — en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote. El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare basado en la técnica de… …   Wikipedia Español

  • Antipatrón de diseño — Saltar a navegación, búsqueda Un antipatrón de diseño es un patrón de diseño que invariablemente conduce a una mala solución para un problema. Al documentarse los antipatrones, además de los patrones de diseño, se dan argumentos a los diseñadores …   Wikipedia Español

  • Código Gray — de dos bits 00 01 11 10 Código Gray de tres bits 000 001 011 010 110 111 101 100 Código Gray de cuatro bits 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 El código binario reflejado o código Gray, nombrado así en …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”