En matemáticas , los ciclos de una permutación π de un finito conjunto S corresponden bijectively a las órbitas del subgrupo generado por π actuación en S . Estas órbitas son subconjuntos de S que se pueden escribir como { c 1 , ..., c l }, de modo que
- π ( do i ) = do i + 1 para i = 1, ..., l - 1 y π ( do l ) = do 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 l de la órbita se denomina longitud del ciclo correspondiente; cuando l = 1, el único elemento 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 las permutaciones consiste en escribir dichas expresiones una tras otra en algún orden. Por ejemplo, deja
ser una permutación que mapea 1 a 2, 6 a 8, etc. Entonces uno 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 tal expresión. [1] Por lo tanto, π = (1 2 4 3) (6 8), sería una forma apropiada de expresar esta permutación.
Hay diferentes formas 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 todo k > 0: s ( k , k ) = 1.
- (2) Para todo 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) Solo hay una forma 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 una 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 permutaciones s ( k - 1, j - 1) 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 yj ciclos e insertar el elemento k en un ciclo existente delante de uno de los elementos k - 1.
Algunos valores
k | j | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | suma | |
1 | 1 | 1 | ||||||||
2 | 1 | 1 | 2 | |||||||
3 | 2 | 3 | 1 | 6 | ||||||
4 | 6 | 11 | 6 | 1 | 24 | |||||
5 | 24 | 50 | 35 | 10 | 1 | 120 | ||||
6 | 120 | 274 | 225 | 85 | 15 | 1 | 720 | |||
7 | 720 | 1,764 | 1,624 | 735 | 175 | 21 | 1 | 5.040 | ||
8 | 5.040 | 13,068 | 13,132 | 6.769 | 1.960 | 322 | 28 | 1 | 40,320 | |
9 | 40,320 | 109.584 | 118,124 | 67,284 | 22,449 | 4.536 | 546 | 36 | 1 | 362,880 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | suma |
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 ver el artículo principal sobre este tema, consulte rencontres numbers .
Propiedades
- (1) Para todo 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 f ( k - 1, j ) permutaciones con k - 1 elementos yj 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 f ( k - 1, j + 1) permutaciones 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.
Algunos valores
k | j | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | suma | |
1 | 0 | 1 | 1 | ||||||||
2 | 1 | 0 | 1 | 2 | |||||||
3 | 2 | 3 | 0 | 1 | 6 | ||||||
4 | 9 | 8 | 6 | 0 | 1 | 24 | |||||
5 | 44 | 45 | 20 | 10 | 0 | 1 | 120 | ||||
6 | 265 | 264 | 135 | 40 | 15 | 0 | 1 | 720 | |||
7 | 1.854 | 1.855 | 924 | 315 | 70 | 21 | 0 | 1 | 5.040 | ||
8 | 14,833 | 14,832 | 7.420 | 2,464 | 630 | 112 | 28 | 0 | 1 | 40,320 | |
9 | 133,496 | 133,497 | 66,744 | 22,260 | 5.544 | 1,134 | 168 | 36 | 0 | 1 | 362,880 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | suma |
Cálculos alternativos
Ejemplo: f (5, 1) = 5 × 1 × 4! - ¡10 × 2 × 3! + 10 × 3 × 2! - ¡5 × 4 × 1! + 1 × 5 × 0!
- = 120 - 120 + 60 - 20 + 5 = 45.
Ejemplo: f (5, 0) = 120 - (5 × 4! - 10 × 3! + 10 × 2! - 5 × 1! + 1 × 0!)
- = 120 - (120 - 60 + 20 - 5 + 1) = 120 - 76 = 44.
- Por cada k > 1:
Ejemplo: f (5, 0) = 4 × (9 + 2) = 4 × 11 = 44
- Por cada k > 1:
Ejemplo: f (5, 0) = 120 × (1/2 - 1/6 + 1/24 - 1/120)
- = 120 × (60/120 - 20/120 + 5/120 - 1/120) = 120 × 44/120 = 44
- donde e es el número de Euler ≈ 2.71828
Ver también
Notas
- ^ Gerstein 1987 , p. 240
- ^ Cameron 1994 , p. 80
- ^ Brualdi 2010 , p. 290
Referencias
- Brualdi, Richard A. (2010), Introducción a la combinatoria (5.a 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