En matemática combinatoria, un índice de ciclo es un polinomio en varias variables que está estructurado de tal manera que la información sobre cómo actúa un grupo de permutaciones en un conjunto se puede leer simplemente a partir de los coeficientes y exponentes. Esta forma compacta de almacenar información en forma algebraica se usa con frecuencia en la enumeración combinatoria .
Cada permutación π de un conjunto finito de objetos se divide en ciclos ; el monomio del índice de ciclo de π es un monomio en las variables a 1 , a 2 ,… que describe el tipo de esta partición (el tipo de ciclo de π): el exponente de a i es el número de ciclos de π de tamaño i . El polinomio de índice de ciclo de un grupo de permutación es el promedio de los monomios de índice de ciclo de sus elementos. El indicador de ciclo de frase también se usa a veces en lugar del índice de ciclo.
Conociendo el polinomio del índice de ciclo de un grupo de permutación, se pueden enumerar clases de equivalencia debido a la acción del grupo. Este es el ingrediente principal del teorema de enumeración de Pólya . Realizar operaciones algebraicas y diferenciales formales en estos polinomios y luego interpretar los resultados de manera combinatoria se encuentra en el núcleo de la teoría de especies .
Grupos de permutación y acciones grupales
Un mapa biyectivo de un conjunto X sobre sí mismo se llama una permutación de X , y el conjunto de todas las permutaciones de X forma un grupo bajo la composición de los mapas, llamado grupo simétrico de X y denotado Sym ( X ). Cada subgrupo de Sym ( X ) se denomina grupo de permutación de grado | X |. [1] Sea G un grupo abstracto con un homomorfismo de grupo φ de G a Sym ( X ). La imagen , φ ( G ), es un grupo de permutación. El homomorfismo de grupo se puede considerar como un medio para permitir que el grupo G "actúe" sobre el conjunto X (utilizando las permutaciones asociadas con los elementos de G ). Tal homomorfismo un grupo se denomina formalmente una acción de grupo y la imagen de la homomorfismo es una representación de permutación de G . Un grupo dado puede tener muchas representaciones de permutación diferentes, correspondientes a diferentes acciones. [2]
Supongamos que el grupo G actúa sobre el conjunto X (es decir, existe una acción de grupo). En aplicaciones combinatorias, el interés está en el conjunto X ; por ejemplo, contando las cosas en X y saber qué estructuras se podrían dejar invariante por G . Se pierde poco al trabajar con grupos de permutación en un entorno de este tipo, por lo que en estas aplicaciones, cuando se considera un grupo, es una representación de permutación del grupo con el que se trabajará y, por lo tanto, se debe especificar una acción de grupo. Los algebristas, por otro lado, están más interesados en los grupos mismos y estarían más interesados en los núcleos de las acciones grupales, que miden cuánto se pierde al pasar del grupo a su representación de permutación. [3]
Representación de ciclos disjuntos de permutaciones
Las permutaciones finitas se representan con mayor frecuencia como acciones de grupo en el conjunto X = {1,2, ..., n}. Una permutación en esta configuración se puede representar mediante una notación de dos líneas. Por lo tanto,
corresponde a una biyección en X = {1, 2, 3, 4, 5} que envía 1 → 2, 2 → 3, 3 → 4, 4 → 5 y 5 → 1. Esto se puede leer en las columnas del notación. Cuando se entiende que la fila superior son los elementos de X en un orden apropiado, solo es necesario escribir la segunda fila. En esta notación de una línea, nuestro ejemplo sería [2 3 4 5 1]. [4] Este ejemplo se conoce como permutación cíclica porque "cicla" los números y una tercera notación sería (1 2 3 4 5). Esta notación de ciclo debe leerse como: cada elemento se envía al elemento de su derecha, pero el último elemento se envía al primero ("cicla" al principio). Con la notación de ciclo, no importa dónde comienza un ciclo, por lo que (1 2 3 4 5) y (3 4 5 1 2) y (5 1 2 3 4) todos representan la misma permutación. La duración de un ciclo es el número de elementos del ciclo.
No todas las permutaciones son permutaciones cíclicas, pero cada permutación puede escribirse como un producto [5] de ciclos disjuntos (que no tienen un elemento común) esencialmente de una manera. [6] Como una permutación puede tener puntos fijos (elementos que no se modifican por la permutación), estos estarán representados por ciclos de longitud uno. Por ejemplo: [7]
Esta permutación es el producto de tres ciclos, uno de longitud dos, uno de longitud tres y un punto fijo. Los elementos de estos ciclos son subconjuntos disjuntos de X y forman una partición de X .
La estructura de ciclo de una permutación se puede codificar como un monomio algebraico en varias variables ( ficticias ) de la siguiente manera: se necesita una variable para cada duración de ciclo distinta de los ciclos que aparecen en la descomposición del ciclo de la permutación. En el ejemplo anterior había tres longitudes de ciclo diferentes, por lo que usaremos tres variables, a 1 , a 2 y a 3 (en general, use la variable a k para que corresponda a la longitud de k ciclos). La variable a i se elevará a la potencia j i ( g ) donde j i ( g ) es el número de ciclos de longitud i en el ciclo de descomposición de la permutación g . Entonces podemos asociar el monomio del índice de ciclo
a la permutación g . El monomio de índice de ciclo de nuestro ejemplo sería un 1 a 2 a 3 , mientras que el monomio de índice de ciclo de la permutación (1 2) (3 4) (5) (6 7 8 9) (10 11 12 13) (14) (15) sería un 1 3 a 2 2 a 4 2 .
Definición
El índice de ciclo de un grupo de la permutación G es la media de los monomios índice de ciclo de todas las permutaciones g en G .
Más formalmente, sea G un grupo de permutación de orden my grado n . Cada permutación g en G tiene una descomposición única en ciclos disjuntos, digamos c 1 c 2 c 3 .... Sea la longitud de un ciclo c denotada por | c |.
Ahora sea j k (g) el número de ciclos de g de longitud k , donde
Asociamos a g el monomio
en las variables a 1 , a 2 , ..., a n .
Entonces el índice de ciclo Z ( G ) de G viene dado por
Ejemplo
Considere el grupo G de simetrías rotacionales de un cuadrado en el plano euclidiano . Tales simetrías están completamente determinadas por las imágenes de solo las esquinas del cuadrado. Al etiquetar estas esquinas 1, 2, 3 y 4 (yendo consecutivamente en el sentido de las agujas del reloj) podemos representar los elementos de G como permutaciones del conjunto X = {1,2,3,4}. [8] La representación de permutación de G consta de las cuatro permutaciones (1 4 3 2), (1 3) (2 4), (1 2 3 4) ye = (1) (2) (3) (4) que representan las rotaciones en sentido antihorario de 90 °, 180 °, 270 ° y 360 ° respectivamente. Tenga en cuenta que la permutación identidad e es la única permutación con puntos fijos en esta representación de G . Como grupo abstracto, G se conoce como el grupo cíclico C 4 , y esta representación de permutación es su representación regular . Los monomios de índice de ciclo son un 4 , un 2 2 , un 4 y un 1 4 respectivamente. Por tanto, el índice de ciclo de este grupo de permutación es:
El grupo C 4 también actúa sobre los pares desordenados de elementos de X de forma natural. Cualquier permutación g enviaría { x , y } → { x g , y g } (donde x g es la imagen del elemento x bajo la permutación g ). [9] El conjunto X ahora es { A , B , C , D , E , F } donde A = {1,2}, B = {2,3}, C = {3,4}, D = {1 , 4}, E = {1,3} y F = {2,4}. Estos elementos se pueden considerar como los lados y diagonales del cuadrado o, en un escenario completamente diferente, como los bordes del gráfico completo K 4 . Actuando sobre este nuevo conjunto, los cuatro elementos del grupo ahora están representados por ( A D C B ) ( E F ), ( AC ) ( BD ) ( E ) ( F ), ( ABCD ) ( EF ) ye = ( A ) ( B ) ( C ) ( D ) ( E ) ( F ) y el índice de ciclo de esta acción es:
El grupo C 4 también puede actuar sobre los pares ordenados de elementos de X de la misma forma natural. Cualquier permutación g enviaría ( x , y ) → ( x g , y g ) (en este caso también habríamos ordenado pares de la forma ( x , x )). Los elementos de X podrían considerarse como los arcos del dígrafo completo D 4 (con bucles en cada vértice). El índice de ciclo en este caso sería:
Tipos de acciones
Como muestra el ejemplo anterior, el índice de ciclo depende de la acción del grupo y no del grupo abstracto. Dado que hay muchas representaciones de permutación de un grupo abstracto, es útil tener alguna terminología para distinguirlas.
Cuando un grupo abstracto se define en términos de permutaciones, es un grupo de permutación y la acción de grupo es el homomorfismo de identidad. Esto se conoce como acción natural .
El grupo simétrico S 3 en su acción natural tiene los elementos [10]
y entonces, su índice de ciclo es:
Un grupo de permutación G en el conjunto X es transitivo si para cada par de elementos de x y Y en X hay al menos una g en G tal que y = x g . Un grupo de permutación transitiva es regular (o algunas veces se lo denomina claramente transitivo ) si la única permutación en el grupo que tiene puntos fijos es la permutación de identidad.
Un grupo de permutación transitiva finito G en el conjunto X es regular si y solo si | G | = | X |. [11] El teorema de Cayley establece que todo grupo abstracto tiene una representación de permutación regular dada por el grupo que actúa sobre sí mismo (como un conjunto) por multiplicación (derecha). A esto se le llama la representación regular del grupo.
El grupo cíclico C 6 en su representación regular contiene las seis permutaciones (la forma de una línea de la permutación se da primero):
- [1 2 3 4 5 6] = (1) (2) (3) (4) (5) (6)
- [2 3 4 5 6 1] = (1 2 3 4 5 6)
- [3 4 5 6 1 2] = (1 3 5) (2 4 6)
- [4 5 6 1 2 3] = (1 4) (2 5) (3 6)
- [5 6 1 2 3 4] = (1 5 3) (2 6 4)
- [6 1 2 3 4 5] = (1 6 5 4 3 2).
Por tanto, su índice de ciclo es:
A menudo, cuando un autor no desea utilizar la terminología de acción de grupo, el grupo de permutación involucrado recibe un nombre que implica cuál es la acción. Los siguientes tres ejemplos ilustran este punto.
El índice de ciclo del grupo de permutación de aristas del gráfico completo en tres vértices
Identificaremos la gráfica completa K 3 con un triángulo equilátero en el plano euclidiano . Esto nos permite usar lenguaje geométrico para describir las permutaciones involucradas como simetrías del triángulo equilátero. Cada permutación en el grupo S 3 de permutaciones de vértice ( S 3 en su acción natural, dada arriba) induce una permutación de arista. Estas son las permutaciones:
- La identidad: no se permuta ningún vértice ni aristas; la contribución es
- Tres reflejos en un eje que pasa por un vértice y el punto medio del borde opuesto: Estos fijan un borde (el que no incide en el vértice) e intercambian los dos restantes; la contribución es
- Dos rotaciones, una en el sentido de las agujas del reloj y la otra en el sentido contrario a las agujas del reloj: crean un ciclo de tres aristas; la contribución es
El índice de ciclo del grupo G de permutaciones de aristas inducidas por permutaciones de vértices de S 3 es
Sucede que el gráfico completo K 3 es isomorfo a su propio gráfico lineal (vértice-borde dual) y, por lo tanto, el grupo de permutación de borde inducido por el grupo de permutación de vértice es el mismo que el grupo de permutación de vértice, es decir, S 3 y el índice de ciclo es Z ( S 3 ). Este no es el caso de gráficos completos en más de tres vértices, ya que estos tienen estrictamente más aristas () que los vértices ( n ).
El índice de ciclo del grupo de permutación de aristas del gráfico completo en cuatro vértices
Esto es completamente análogo al caso de los tres vértices. Estas son las permutaciones de vértices ( S 4 en su acción natural) y las permutaciones de aristas ( S 4 actuando sobre pares desordenados) que inducen:
- La identidad: esta permutación mapea todos los vértices (y por lo tanto, los bordes) a sí mismos y la contribución es
- Seis permutaciones que intercambian dos vértices: Estas permutaciones conservan el borde que conecta los dos vértices así como el borde que conecta los dos vértices no intercambiados. Los bordes restantes forman dos ciclos de dos y la contribución es
- Ocho permutaciones que fijan un vértice y producen un ciclo de tres para los tres vértices no fijos: Estas permutaciones crean dos ciclos de aristas de tres, uno que contiene los que no inciden en el vértice y otro que contiene los que inciden en el vértice; la contribución es
- Tres permutaciones que intercambian dos pares de vértices al mismo tiempo: estas permutaciones conservan los dos bordes que conectan los dos pares. Los bordes restantes forman dos ciclos de dos y la contribución es
- Seis permutaciones que recorren los vértices en un ciclo de cuatro: Estas permutaciones crean un ciclo de cuatro aristas (las que se encuentran en el ciclo) e intercambian las dos aristas restantes; la contribución es
Podemos visualizar los tipos de permutaciones geométricamente como simetrías de un tetraedro regular . Esto produce la siguiente descripción de los tipos de permutación.
- La identidad.
- Reflexión en el plano que contiene una arista y el punto medio de la arista opuesta.
- Rotación de 120 grados sobre el eje que pasa por un vértice y el punto medio de la cara opuesta.
- Rotación de 180 grados alrededor del eje que conecta los puntos medios de dos bordes opuestos.
- Seis rotorreflexiones de 90 grados.
El índice de ciclo del grupo de permutación de aristas G de K 4 es:
El índice de ciclo de las permutaciones de caras de un cubo.
Considere un cubo ordinario en tres espacios y su grupo de simetrías (automorfismos), lo llaman C . Permuta las seis caras del cubo. (También podríamos considerar permutaciones de aristas o permutaciones de vértices). Hay veinticuatro automorfismos.
- La identidad:
- Existe una de esas permutaciones y su contribución es
- Seis rotaciones faciales de 90 grados:
- Giramos sobre el eje que pasa por los centros del rostro y el rostro opuesto. Esto fijará la cara y la cara opuesta y creará un ciclo de cuatro caras paralelas al eje de rotación. La contribución es
- Tres rotaciones faciales de 180 grados:
- Giramos sobre el mismo eje que en el caso anterior, pero ahora no hay cuatro ciclos de caras paralelas al eje, sino dos dos ciclos. La contribución es
- Ocho rotaciones de vértices de 120 grados:
- Esta vez giramos sobre el eje que pasa por dos vértices opuestos (los extremos de una diagonal principal). Esto crea dos tres ciclos de caras (las caras incidentes en el mismo vértice forman un ciclo). La contribución es
- Seis rotaciones de borde de 180 grados:
- Estas rotaciones de aristas giran alrededor del eje que pasa por los puntos medios de aristas opuestas no incidentes en la misma cara y paralelas entre sí e intercambia las dos caras incidentes en la primera arista, las dos caras incidentes en la segunda arista y la dos caras que comparten dos vértices pero sin arista con las dos aristas, es decir, hay tres dos ciclos y la contribución es
La conclusión es que el índice de ciclo del grupo C es
Índices de ciclo de algunos grupos de permutación
Grupo de identidad E n
Este grupo contiene una permutación que corrige cada elemento (debe ser una acción natural).
Grupo cíclico C n
Un grupo cíclico , C n es el grupo de rotaciones de un n -gon regular , es decir, n elementos igualmente espaciados alrededor de un círculo. Este grupo tiene φ ( d ) elementos de orden d para cada divisor d de n , donde φ ( d ) es la función φ de Euler , dando el número de números naturales menores que d que son relativamente primos ad . En la representación regular de C n , una permutación de orden d tiene n / d ciclos de longitud d , así: [12]
Grupo diedro D n
El grupo diedro es como el grupo cíclico , pero también incluye reflejos. En su acción natural,
Grupo alterno A n
El índice de ciclo del grupo alterno en su acción natural como grupo de permutación es
El numerador es 2 para las permutaciones pares y 0 para las permutaciones impares. El 2 es necesario porque.
Grupo simétrico S n
El índice de ciclo del grupo simétrico S n en su acción natural viene dado por la fórmula:
que también se puede expresar en términos de polinomios de Bell completos :
Esta fórmula se obtiene contando cuántas veces puede ocurrir una forma de permutación dada. Hay tres pasos: primero particione el conjunto de n etiquetas en subconjuntos, donde haysubconjuntos de tamaño k . Cada uno de estos subconjuntos generaciclos de longitud k . Pero no distinguimos entre ciclos del mismo tamaño, es decir, están permutados por. Esto produce
Existe una fórmula recursiva útil para el índice de ciclo del grupo simétrico. Colocary considere el tamaño l del ciclo que contiene n , donde Existen formas de elegir el resto elementos del ciclo y cada elección genera diferentes ciclos.
Esto produce la recurrencia
o
Aplicaciones
A lo largo de esta sección, modificaremos ligeramente la notación de los índices cíclicos al incluir explícitamente los nombres de las variables. Así, para el grupo de permutación G escribiremos ahora:
Let G ser un grupo que actúa sobre el conjunto X . G también induce una acción sobre los k -subconjuntos de X y sobre las k -tuplas de elementos distintos de X (ver #Ejemplo para el caso k = 2), para 1 ≤ k ≤ n . Sean f k y F k el número de órbitas de G en estas acciones, respectivamente. Por convención, establecemos f 0 = F 0 = 1. Tenemos: [13]
a) La función generadora ordinaria para f k viene dada por:
- y
b) La función generadora exponencial para F k viene dada por:
Deje que G sea un grupo que actúa sobre el conjunto X y h una función de X a Y . Para cualquier g en G , h ( x g ) también es una función de X a Y . Por lo tanto, G induce una acción sobre el conjunto Y X de todas las funciones de X a Y . El número de órbitas de esta acción es Z ( G ; b , b , ..., b ) donde b = | Y |. [14]
Este resultado se deriva del lema de conteo de órbitas (también conocido como lema de Not Burnside, pero tradicionalmente llamado lema de Burnside) y la versión ponderada del resultado es el teorema de enumeración de Pólya .
El índice de ciclo es un polinomio en varias variables y los resultados anteriores muestran que ciertas evaluaciones de este polinomio dan resultados combinatoriamente significativos. Como polinomios, también se pueden sumar, restar, diferenciar e integrar formalmente. El área de la combinatoria simbólica proporciona interpretaciones combinatorias de los resultados de estas operaciones formales.
La cuestión de cómo se ve la estructura del ciclo de una permutación aleatoria es una cuestión importante en el análisis de algoritmos . Se puede encontrar una descripción general de los resultados más importantes en las estadísticas de permutación aleatoria .
Notas
- ^ Dixon y Mortimer 1996 , pág. 2, sección 1.2 Grupos simétricos
- ^ Cameron 1994 , págs. 227–228
- ^ Cameron 1994 , pág. 231, sección 14.3
- ^ Este estilo de notación se encuentra con frecuencia en la literatura informática.
- ^ Las permutaciones cíclicas son funciones y el término producto realmente significa composición de estas funciones.
- ^ Hasta las diferentes formas en que se puede escribir un ciclo y el hecho de que los ciclos inconexos se desplazan para poder escribirlos en cualquier orden.
- ^ Roberts y Tesman 2009 , pág. 473
- ^ Técnicamente estamos utilizando la noción de equivalencia de las acciones de grupo, en sustitución de G actúa sobre las esquinas de la plaza por la representación permutación de G actúa sobre X . A los efectos de la exposición, es mejor pasar por alto estos detalles.
- ^ Esta notación es común entre geómetras y combinatorios. Se usa en lugar del g (x) más común por razones tradicionales.
- ^ Existe una convención para no escribir los puntos fijos en la notación del ciclo para una permutación, pero estos deben estar representados en el índice del ciclo.
- ^ Dixon y Mortimer 1996 , pág. 9, Corolario 1.4A (iii)
- ^ van Lint y Wilson 1992 , pág. 464, ejemplo 35.1
- ^ Cameron 1994 , pág. 248, Proposición 15.3.1
- ^ van Lint y Wilson 1992 , pág. 463, Teorema 35.1
Referencias
- Brualdi, Richard A. (2010), "14. Pólya Counting", Introductory Combinatorics (5ª ed.), Upper Saddle River, Nueva Jersey: Prentice Hall, págs. 541–575, ISBN 978-0-13-602040-0
- Cameron, Peter J. (1994), "15. Enumeración bajo acción de grupo", Combinatoria: temas, técnicas, algoritmos , Cambridge: Cambridge University Press, págs. 245-256, ISBN 0-521-45761-0
- Dixon, John D .; Mortimer, Brian (1996), Permutation Groups , Nueva York: Springer, ISBN 0-387-94599-7
- Roberts, Fred S .; Tesman, Barry (2009), "8.5 The Cycle Index", Applied Combinatorics (2ª ed.), Boca Raton: CRC Press, págs. 472–479, ISBN 978-1-4200-9982-9
- Tucker, Alan (1995), "9.3 The Cycle Index", Applied Combinatorics (3.ª ed.), Nueva York: Wiley, págs. 365–371, ISBN 0-471-59504-7
- van Lint, JH; Wilson, RM (1992), "35. Polya teoría del conteo", Un curso de combinatoria , Cambridge: Cambridge University Press, págs. 461–474, ISBN 0-521-42260-4
enlaces externos
- Marko Riedel, el teorema de enumeración de Pólya y el método simbólico
- Marko Riedel, Índices de ciclo del operador conjunto / multiset y la fórmula exponencial
- Harald Fripertinger (1997). "Índices de ciclo de grupos lineales, afines y proyectivos" . Álgebra lineal y sus aplicaciones . 263 : 133-156. doi : 10.1016 / S0024-3795 (96) 00530-7 .
- Harald Fripertinger (1992). "Enumeración en Teoría Musical" . Beiträge zur Elektronischen Musik . 1 .