Ciclos y puntos fijos

En matemáticas , los ciclos de una permutación π de un conjunto finito S corresponden biyectivamente a las órbitas del subgrupo generado por π actuando sobre S. Estas órbitas son subconjuntos de S que pueden escribirse como { c ₁ , ..., c _n } , tales que

π ( c _i ) = c _{i + 1} para i = 1, ..., n − 1 , y π ( c _n ) = c ₁ .

El ciclo correspondiente de π se escribe como ( c ₁ c ₂ ... c _n ); esta expresión no es única ya que c ₁ puede elegirse como cualquier elemento de la órbita.

El tamaño n de la órbita se denomina longitud del ciclo correspondiente; cuando n = 1 , el elemento individual en la órbita se denomina punto fijo de la permutación.

Una permutación se determina dando una expresión para cada uno de sus ciclos, y una notación para permutaciones consiste en escribir dichas expresiones una tras otra en algún orden. Por ejemplo, sea

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

ser una permutación que asigna 1 a 2, 6 a 8, etc. Entonces se puede escribir

π = ( 1 2 4 3 ) ( 5 ) ( 6 8 ) (7) = (7) ( 1 2 4 3 ) ( 6 8 ) ( 5 ) = ( 4 3 1 2 ) ( 8 6 ) ( 5 ) ( 7) =...

Aquí 5 y 7 son puntos fijos de π , ya que π (5) = 5 y π (7) = 7. Es típico, pero no necesario, no escribir los ciclos de longitud uno en dicha expresión. ^[1] Por lo tanto, π  = (1 2 4 3)(6 8), sería una forma apropiada de expresar esta permutación.

Hay diferentes maneras de escribir una permutación como una lista de sus ciclos, pero el número de ciclos y sus contenidos están dados por la partición de S en órbitas, y por lo tanto son los mismos para todas esas expresiones.

El número de Stirling sin signo del primer tipo, s ( k , j ), cuenta el número de permutaciones de k elementos con exactamente j ciclos disjuntos. ^{[2] [3]}

(1) Para cada k > 0 : s ( k , k ) = 1.

(2) Para cada k > 0 : s ( k , 1) = ( k − 1)!.

(3) Para cada k > j > 1, s ( k , j ) = s ( k − 1, j − 1) + s ( k − 1, j )·( k − 1)

(1) Sólo hay una manera de construir una permutación de k elementos con k ciclos: cada ciclo debe tener una longitud de 1, por lo que cada elemento debe ser un punto fijo.

(2.a) Cada ciclo de longitud k puede escribirse como permutación del número 1 a k ; hay k ! de estas permutaciones.

(2.b) Hay k formas diferentes de escribir un ciclo dado de longitud k , por ejemplo, ( 1 2 4 3 ) = ( 2 4 3 1 ) = ( 4 3 1 2 ) = ( 3 1 2 4 ).

(2.c) Finalmente: s ( k , 1) = k !/ k = ( k − 1)!.

(3) Hay dos formas diferentes de construir una permutación de k elementos con j ciclos:

(3.a) Si queremos que el elemento k sea un punto fijo, podemos elegir una de las s ( k − 1, j − 1) permutaciones con k − 1 elementos y j − 1 ciclos y agregar el elemento k como un nuevo ciclo de longitud 1.

(3.b) Si queremos que el elemento k no sea un punto fijo, podemos elegir una de las s ( k − 1, j ) permutaciones con k − 1 elementos y j ciclos e insertar el elemento k en un ciclo existente delante de uno de los k − 1 elementos.

El valor f ( k , j ) cuenta el número de permutaciones de k elementos con exactamente j puntos fijos. Para el artículo principal sobre este tema, consulte rencontres numbers .

(1) Para cada j < 0 o j > k  : f ( k , j ) = 0.

(2) f (0, 0) = 1.

(3) Para cada k > 1 y k ≥ j ≥ 0, f ( k , j ) = f ( k − 1, j − 1) + f ( k − 1, j )·( k − 1 − j ) + f ( k − 1, j + 1)·( j + 1)

(3) Hay tres métodos diferentes para construir una permutación de k elementos con j puntos fijos:

(3.a) Podemos elegir una de las permutaciones f ( k − 1, j − 1) con k − 1 elementos y j − 1 puntos fijos y agregar el elemento k como un nuevo punto fijo.

(3.b) Podemos elegir una de las permutaciones f ( k − 1, j ) con k − 1 elementos y j puntos fijos e insertar el elemento k en un ciclo existente de longitud > 1 delante de uno de los ( k − 1) − j elementos.

(3.c) Podemos elegir una de las permutaciones f ( k − 1, j + 1) con k − 1 elementos y j + 1 puntos fijos y unir el elemento k con uno de los j + 1 puntos fijos en un ciclo de longitud 2.

• Permutación cíclica
• Notación de ciclo

• Brualdi, Richard A. (2010), Combinatoria introductoria (5.ª ed.), Prentice-Hall, ISBN 978-0-13-602040-0
• Cameron, Peter J. (1994), Combinatoria: temas, técnicas, algoritmos , Cambridge University Press, ISBN 0-521-45761-0
• Gerstein, Larry J. (1987), Matemáticas discretas y estructuras algebraicas , WH Freeman and Co., ISBN 0-7167-1804-9