G tiene 2 puntos fijos, 1 de 2 ciclos y 3 de 4 ciclos B tiene 4 puntos fijos y 6 de 2 ciclos GB tiene 2 puntos fijos y 2 de 7 ciclosP * (1,2,3,4) T = (4,1,3,2) T
Permutación de cuatro elementos con 1 punto fijo y 1 3 ciclos
π ( 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 se puede elegir que c 1 sea cualquier elemento de la órbita.
El tamaño n de la órbita se denomina longitud del ciclo correspondiente; cuando n = 1 , el único elemento en la órbita se llama 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, dejemos
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 su contenido vienen dados por la partición de S en órbitas y, por lo tanto, son las mismas para todas esas expresiones.
Contando 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 de las propiedades
(1) Sólo hay una forma de construir una permutación de k elementos con k ciclos: cada ciclo debe tener longitud 1, por lo que cada elemento debe ser un punto fijo.
(2.a) Cada ciclo de longitud k puede escribirse como una permutación del número 1 en 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
Contando 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 consultar el artículo principal sobre este tema, consulte números de rencontres .
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 de 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 f ( k − 1, j ) permutaciones 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 a un ciclo de longitud 2.
