Diferencia entre revisiones de «Permutación cíclica»
Contenido eliminado Contenido añadido
m link |
|||
| Línea 1: | Línea 1: | ||
{{Fusionar|Ciclo (permutación)}} |
|||
[[Archivo:050712 perm 3.png|thumb|Un ciclo que deja fijos a los elementos 2 y 5 y mueve cíclicamente al resto.]] |
|||
Una '''permutación circular''' es una [[permutación]] que se aplica a conjuntos ordenados 'circulares', es decir, que no tienen principio ni final. Para trabajar con ellas se fija arbitráriamente un elemento como el primero. Cabe destacar que aunque pueda parecerlo, no se debe considerar una permutación circular como una permutación típica ya que tiene algunas propiedades que no son aplicables a las otras. |
|||
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 <math>n\geq2</math> y <math>2\leq r\leq n</math>. Un '''ciclo de longitud <math>r</math>''' o r-ciclo de <math>S_n</math> es una [[permutación]] <math>\sigma</math> tal que del conjunto <math>\{1,2,...,n\}</math> hay <math>r</math> elementos diferentes secuenciados, <math>a_1,a_2,...,a_r</math>, para los cuales se cumple que: |
|||
:<math>M(\sigma) = \{a_1,a_2,...,a_r\}</math>, de tal manera que <math>\sigma(x)=x</math> si <math>x\neq a_i \forall i</math>. |
|||
:<math>\sigma(a_1)=a_2,\sigma(a_2)=a_3,...,\sigma(a_{r-1})=a_r</math> y <math>\sigma(a_r)=a_1</math>. |
|||
== Ejemplos == |
|||
[[Archivo:050712 perm 2.png|right|Ejemplo de un ciclo]] |
|||
* La permutación <math>\sigma</math> es un ciclo que no fija ningún elemento. Por ello, también se dice que es una permutación cíclica. |
|||
:<math> |
|||
\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}</math> |
|||
[[Archivo:050712 perm 1.png|right|Ejemplo de una permutación formada por dos ciclos]] |
|||
* La permutación <math>\omega</math> no es un ciclo, ya que es una permutación compuesta por dos ciclos. |
|||
:<math> |
|||
\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}</math> |
|||
:De hecho, se demuestra que cualquier permutación puede descomponerse como producto de ciclos disjuntos.<ref>Birkhoff & MacLane, ''A survey of modern algebra'', McMillan Publishing, 1977. ISBN 0-02-310070-2</ref> |
|||
* Transposición: es un ciclo de longitud 2, es decir, un 2-ciclo. |
|||
== Propiedades == |
|||
'''Notación: ''' Si un elemento <math>a</math> de un conjunto <math>A</math> se ve 'afectado' por un ciclo <math>\sigma:A\to A</math> entonces decimos que <math>a\in M(\sigma)</math>. |
|||
* Sea <math>\sigma</math> un ciclo de longitud <math>r</math>, entonces |
|||
: Si <math>a \in M(\sigma)</math> entonces se puede escribir como |
|||
:::<math>\sigma = (a,\sigma(a),...,\sigma^{r-1}(a))</math> |
|||
:y <math>r</math> es el mínimo natural <math>k\geq1 : \sigma^k(a)=a</math>. |
|||
* Sea <math>\sigma</math> un ciclo de longitud <math>r</math>, entonces |
|||
:<math>\sigma^r = Id</math> y además <math>r</math> es el mínimo natural <math>k\geq1 : \sigma^k = Id</math>. |
|||
:De ésta proposición se deduce directamente el segundo enunciado de la proposición 1. |
|||
* Sea <math>\sigma</math> un ciclo de longitud <math>r</math>, entonces |
|||
| ⚫ | |||
== Referencias == |
|||
{{listaref}} |
|||
== Véase también == |
|||
* [[Permutación]] (concepto previo). |
|||
* [[Grupo simétrico]]. |
|||
[[Categoría:Permutaciones]] |
|||
[[Categoría:Álgebra abstracta]] |
[[Categoría:Álgebra abstracta]] |
||
[[Categoría:Teoría de conjuntos]] |
[[Categoría:Teoría de conjuntos]] |
||
[[Categoría:Combinatoria enumerativa]] |
|||
Revisión del 18:09 27 mar 2013
Una permutación circular es una permutación que se aplica a conjuntos ordenados 'circulares', es decir, que no tienen principio ni final. Para trabajar con ellas se fija arbitráriamente un elemento como el primero. Cabe destacar que aunque pueda parecerlo, no se debe considerar una permutación circular como una permutación típica ya que tiene algunas propiedades que no son aplicables a las otras.
