π ( c i ) = c i + 1 para i = 1, ..., n − 1 , y π ( c n ) = c 1 .
El ciclo correspondiente de π se escribe como ( c 1 c 2 ... c n ); esta expresión no es única ya que c 1 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
ser una permutación que asigna 1 a 2, 6 a 8, etc. Entonces se puede escribir
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.
Contar permutaciones por número de ciclos
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]
Propiedades
(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)
Razones para las propiedades
(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.
Algunos valores
Contar permutaciones por número de puntos fijos
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 .
Propiedades
(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)
Razones para las propiedades
(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.
