# Cicle (permutació)

En matemàtiques, i en particular en teoria de grups, una permutació cíclica és una permutació dels elements d'un conjunt X que transforma els elements d'un subconjunt S de X els uns en els altres de manera cíclica, mentre que manté fixos (és a dir, transforma en ells mateixos) la resta d'elements de X. Per exemple, la permutació de {1, 2, 3, 4} que envia 1 a 2, 2 a 3, 3 a 4 i 4 a 1 és un cicle, mentre que la permutació que envia 1 a 3, 3 a 1, 2 a 4 i 4 a 2 no ho és (permuta de manera separada els parells {1, 3} i {2, 4}).
Un cicle d'una permutació és un subconjunt dels elements que s'intercanvien de forma cíclica. El conjunt S s'anomena òrbita del cicle. Tota permutació d'un nombre finit d'elements es pot descompondre en un nombre finit de cicles amb òrbites disjuntes. En alguns contextos, hom anomena cicle a una permutació cíclica.

## Definició

Hom diu que una permutació és una permutació cíclica si i només si consisteix d'un sol cicle no trivial (un cicle de longitud > 1).
Exemple:
    ${\begin{aligned}&{\begin{pmatrix}1&2&3&4&5&6&7&8\\4&2&7&6&5&8&1&3\end{pmatrix}}&=\\=&{\begin{pmatrix}1&4&6&8&3&7&2&5\\4&6&8&3&7&1&2&5\end{pmatrix}}&=\\=&(146837)(2)(5)\end{aligned}}$         (1)
Alguns autors restringeixen la definició a aquelles permutacions que tenen exactament un cicle (és a dir, no s'hi permeten punts fixos).
Exemple:
    ${\begin{aligned}&{\begin{pmatrix}1&2&3&4&5&6&7&8\\4&5&7&6&8&2&1&3\end{pmatrix}}&=\\=&{\begin{pmatrix}1&4&6&2&5&8&3&7\\4&6&2&5&8&3&7&1\end{pmatrix}}&=\\=&(14625837)\end{aligned}}$         (2)
Més formalment, hom diu que una permutació d'un conjunt X, que és una funció bijectiva $\sigma :X\to X$, és un cicle si l'acció sobre X del subgrup generat per $\sigma$ té com a màxim una òrbita amb més d'un element. Aquest concepte s'usa sobretot si X és un conjunt finit; en aquest cas, és evident que l'òrbita més gran, S, també és finita. Sigui $s_{0}$ un element qualsevol de S, i escrivim $s_{i}=\sigma ^{i}(s_{0})\,$ per a qualsevol $i\in \mathbf {Z}$. Si S és finit, llavors existeix un nombre mínim $k\geq 1$ tal que $s_{k}=s_{0}$. Aleshores $S=\{s_{0},s_{1},\ldots ,s_{k-1}\}$, i $\sigma$ és la permutació definida per
    $\sigma (s_{i})=s_{i+1}\quad {\mbox{per }}0\leq i<k$
i $\sigma (x)=x$ per a qualsevol element de $X\setminus S$. Els elements que no queden fixats per $\sigma$ es poden visualitzar com
    $s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{k-1}\mapsto s_{k}=s_{0}$.
Hom pot escriure un cicle emprant la notació de cicles compacta $\sigma =(s_{0}~s_{1}~\dots ~s_{k-1})$ (notem que no hi ha comes entre els elements, per evitar confusions amb una k-tupla). La longitud d'un cicle és el nombre d'elements de la seva òrbita més gran. Un cicle de longitud k també es diu k-cicle.
Hom diu que l'òrbita d'un 1-cicle és un punt fix de la permutació, però pensat com a permutació, tot 1-cicle és la permutació identitat. Quan s'utilitza la notació de cicles, hom acostuma a suprimir els 1-cicles, si no hi ha confusió.

## Propietats bàsiques

Un dels resultats bàsics dels grups simètrics estableix que tota permutació es pot expressar com a producte de cicles disjunts (més precisament: cicles amb òrbites disjuntes); aquests cicles disjunts commuten els uns amb els altres, i l'expressió de la permutació és única llevat de l'ordre dels cicles (observem, però, que la notació de cicles no és única: cada k-cicle es pot escriure de k maneres diferents, depenent de l'elecció de $s_{0}$ en la seva òrbita). Per tant, el multiconjunt de les longituds dels cicles expressats d'aquesta forma (l'indicador de cicles) està unívocament determinat per la permutació, i també determina tant la signatura com la classe de conjugació de la permutació del grup simètric.
El nombre de k-cicles del grup simètric S$_n$ ve donat, per $1\leq k\leq n$, per les següents fórmules equivalents:
    ${\begin{aligned}{\binom {n}{k}}(k-1)!&={\frac {n(n-1)\cdots (n-k+1)}{k}}\\&={\frac {n!}{(n-k)!k}}\end{aligned}}$
Un k-cicle té signatura (−1)$^{k−1}$.

## Transposicions

Una transposició és un cicle amb dos elements. Per exemple, la permutació de {1, 2, 3, 4} que envia 1 a 1, 2 a 4, 3 a 3 i 4 a 2 és una transposició (la transposició que intercanvia 2 i 4).

### Propietats

Qualsevol permutació es pot expressar com a composició (producte) de transposicions; formalment, les transposicions són generadores del grup. De fet, si hom pren $a=1$, $b=2$, ..., $e=5$, llavors qualsevol permutació es pot expressar com a producte de transposicions adjacents, és a dir, com a transposicions de la forma $(k~~k+1)$; en aquest cas, $(1~2)$, $(2~3)$, $(3~4)$ i $(4~5)$. Això és una conseqüència del fet que qualsevol transposició es pot expressar com a producte de transposicions adjacents. Concretament, hom pot expressar la transposició $(k~~l)$ on $k<l$ movent k a la posició de l un pas a cada iteració, i llavors movent l a la posició original de k, la qual cosa intercanvia aquests dos elements i no realitza cap més canvi:
    $(k~~l)=(k~~k+1)\cdot (k+1~~k+2)\cdots (l-1~~l)\cdot (l-2~~l-1)\cdots (k~~k+1)$.
La descomposició d'una permutació en producte de transposicions s'obté, per exemple, escrivint la permutació com a producte de cicles disjunts, i després separant iterativament cadascun dels cicles de longitud ≥3 en producte d'una transposició i un cicle de longitud igual a la longitud del cicle original menys 1:
    $(a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z)$
Això significa que l'objectiu inicial és moure $a$ cap a $b$, $b$ cap a $c$, $y$ cap a $z$ i finalment $z$ cap a $a$. En comptes d'això, es poden desplaçar els elements mantenint $a$ al seu lloc, primer executant el factor dret (de la manera habitual en la notació d'operadors, i seguint la convenció de l'article Permutació). Amb aquesta operació hem aconseguit moure $z$ a la posició de $b$, de tal manera que, després de la primera permutació, els elements $a$ i $z$ encara no estan a les seves posicions finals. La transposició $(a~b)$, executada a continuació, identifica l'element $z$ mitjançant l'índex de $b$, per tal d'intercanviar el que inicialment eren $a$ i $z$.
Un dels resultats principals sobre grups simètrics afirma que o bé totes les descomposicions d'una permutació donada tenen un nombre parell de transposicions, o bé tenen totes un nombre senar de transposicions. Això permet que la paritat d'una permutació sigui un concepte ben definit (és a dir, no hi ha ambigüitat possible, perquè davant de dues descomposicions diferents, són ambdues o bé parelles o bé senars).

## Referències

* ↑ Bogart, Kenneth P. Introductory Combinatorics. 2a edició. Harcourt, Brace, Jovanovich, 1990, p. 486. ISBN 0-15-541576-X.
* ↑ Gross, Jonathan L. Combinatorial Methods with Computer Applications. Chapman & Hall/CRC, 2008, p. 29. ISBN 978-1-58488-743-0.
* ↑ Fraleigh 1993, p. 103
* ↑ Rotman 2006, p. 108
* ↑ Sagan 1991, p. 2
* ↑ Per tal de ser tècnicament correcte, una factorització hauria de contenir un 1-cicle per a cada punt fix de la permutació (vegeu Rotman 2006, pàg. 113-114).
* ↑ Rotman 2006, pàg. 117, 121
* ↑ Rotman 2006, Prop. 2.35
* ↑ Rotman 2006, p. 122

## Bibliografia

* Anderson, Marlow; Feil, Todd. A First Course in Abstract Algebra. 2a edició. Chapman & Hall/CRC, 2005). ISBN 1-58488-515-7.
* Fraleigh, John. A first course in abstract algebra. 5a edició. Addison Wesley, 1993. ISBN 978-0-201-53467-2.
* Rotman, Joseph J. A First Course in Abstract Algebra with Applications. 3a edició. Prentice-Hall, 2006. ISBN 978-0-13-186267-8.
* Sagan, Bruce E. The Symmetric Group / Representations, Combinatorial Algorithms & Symmetric Functions. Wadsworth & Brooks/Cole, 1991. ISBN 978-0-534-15540-7.

## Enllaços externs

* Permutations as a Product of Transpositions
Aquest article conté material de la pàgina cycle a PlanetMath, llicenciat sota la Llicència de Creative Commons Reconeixement i Compartir-Igual.
Viccionari