índice de ciclo

En matemáticas combinatorias , un índice de ciclo es un polinomio de 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 utiliza con frecuencia en enumeración combinatoria .

Cada permutación π de un conjunto finito de objetos se divide en ciclos ; el monomio índice de ciclo de π es un monomio en variables a ₁ , a ₂ , … que describe el tipo de ciclo de esta partición: 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 permutaciones es el promedio de los monomios de índice de ciclo de sus elementos. La frase indicador de ciclo también se utiliza a veces en lugar de índice de ciclo .

Conociendo el polinomio del índice de ciclo de un grupo de permutaciones, 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 con estos polinomios y luego interpretar los resultados combinatoriamente es el núcleo de la teoría de las especies .

Grupos de permutación y acciones grupales.

Una aplicación biyectiva de un conjunto X sobre sí mismo se llama permutación de X , y el conjunto de todas las permutaciones de X forma un grupo bajo la composición de asignaciones, 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 puede considerarse 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 de grupo se denomina formalmente acción de grupo y la imagen del homomorfismo es una representación de permutación de G . Un grupo determinado 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 grupal). En aplicaciones combinatorias el interés está en el conjunto X ; por ejemplo, contar cosas en X y saber qué estructuras G podría dejar invariantes . 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 otra parte, están más interesados ​​en los grupos mismos y estarían más preocupados por los núcleos de las acciones del grupo, que miden cuánto se pierde al pasar del grupo a su representación de permutación. ^[3]

Representación de ciclo disjunto de permutaciones.

Las permutaciones finitas se representan con mayor frecuencia como acciones grupales 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. De este modo,

${\displaystyle \left({\begin{matrix}1&2&3&4&5\\2&3&4&5&1\end{matrix}}\right)}$

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 de la notación. Cuando se entiende que la fila superior son los elementos de X en un orden apropiado, sólo es necesario escribir la segunda fila. En esta notación unifilar, 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 (hace un "ciclo" hasta el principio). Con la notación cíclica, 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) 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 se puede escribir como un producto ^[5] de ciclos disjuntos (que no tienen ningún elemento común) esencialmente de una manera. ^[6] Como una permutación puede tener puntos fijos (elementos que no cambian por la permutación), estos estarán representados por ciclos de longitud uno. Por ejemplo: ^[7]

${\displaystyle \left({\begin{matrix}1&2&3&4&5&6\\2&1&3&5&6&4\end{matrix}}\right)=(12)(3)(456).}$

Esta permutación es el producto de tres ciclos, uno de longitud dos, otro 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 del 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 longitud 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 duraciones de ciclo diferentes, por lo que usaremos tres variables, a ₁ , a ₂ y a ₃ (en general, use la variable a _k para corresponder a la duración 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 la descomposición cíclica de la permutación g . Entonces podemos asociar el monomio del índice del ciclo.

${\displaystyle \prod _{k=1}^{n}a_{k}^{j_{k}(g)}}$

a la permutación g . El monomio de índice de ciclo de nuestro ejemplo sería a ₁ a ₂ a ₃ , 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) sería un ₁ un ₂ ² un ₄ ² .

Definición

El índice de ciclo de un grupo de permutaciones G es el promedio de los monomios del índice de ciclo de todas las permutaciones g en G.

Más formalmente, sea G un grupo de permutaciones de orden m y grado n . Cada permutación g en G tiene una descomposición única en ciclos disjuntos, digamos c ₁ c ₂ c ₃ .... Sea la duración de un ciclo c la que se denota por | c  |.

Ahora sea j _k ( g ) el número de ciclos de g de longitud k , donde

${\displaystyle 0\leq j_{k}(g)\leq \lfloor n/k\rfloor {\mbox{ and }}\sum _{k=1}^{n}k\,j_{k}(g)=n.}$

Asociamos a g el monomio

${\displaystyle \prod _{c\in g}a_{|c|}=\prod _{k=1}^{n}a_{k}^{j_{k}(g)}}$

en las variables a ₁ , a ₂ , ..., a _n .

Entonces el índice de ciclo Z ( G ) de G viene dado por

${\displaystyle Z(G)={\frac {1}{|G|}}\sum _{g\in G}\prod _{k=1}^{n}a_{k}^{j_{k}(g)}.}$

Ejemplo

Considere el grupo G de simetrías rotacionales de un cuadrado en el plano euclidiano . Sus elementos están completamente determinados por las imágenes de apenas las esquinas de la plaza. Al etiquetar estas esquinas 1, 2, 3 y 4 (consecutivamente en el sentido de las agujas del reloj, digamos) 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) y e = (1)(2)(3)(4) que representan las rotaciones en sentido antihorario de 90°, 180°, 270° y 360° respectivamente. Observe 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 grupo cíclico C ₄ , y esta representación de permutación del mismo es su representación regular . Los monomios del índice de ciclo son a ₄ , a ₂ ² , a ₄ y a ₁ ⁴ respectivamente. Por tanto, el índice de ciclo de este grupo de permutaciones es:

${\displaystyle Z(C_{4})={\frac {1}{4}}\left(a_{1}^{4}+a_{2}^{2}+2a_{4}\right).}$

El grupo C ₄ 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 pueden considerarse como los lados y las diagonales del cuadrado o, en un contexto completamente diferente, como los bordes del gráfico completo K ₄ . 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 ) y e = ( A ) ( B )( C )( D )( E )( F ), y el índice de ciclo de esta acción es:

${\displaystyle Z(C_{4})={\frac {1}{4}}\left(a_{1}^{6}+a_{1}^{2}a_{2}^{2}+2a_{2}a_{4}\right).}$

El grupo C ₄ 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 ₄ (con bucles en cada vértice). El índice de ciclo en este caso sería:

${\displaystyle Z(C_{4})={\frac {1}{4}}\left(a_{1}^{16}+a_{2}^{8}+2a_{4}^{4}\right).}$

Tipos de acciones

Como muestra el ejemplo anterior, el índice del 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 permutaciones y la acción del grupo es el homomorfismo de identidad . Esto se conoce como acción natural .

El grupo simétrico S ₃ en su acción natural tiene los elementos ^[10]

${\displaystyle S_{3}=\{e,(23),(12),(123),(132),(13)\}}$

y entonces su índice de ciclo es:

${\displaystyle Z(S_{3})={\frac {1}{6}}\left(a_{1}^{3}+3a_{1}a_{2}+2a_{3}\right).}$

Un grupo de permutación G en el conjunto X es transitivo si para cada par de elementos x e y en X hay al menos un g en G tal que y = x ^g . Un grupo de permutaciones transitivas es regular (o a veces denominado marcadamente transitivo ) si la única permutación en el grupo que tiene puntos fijos es la permutación identidad.

Un grupo de permutaciones transitivas finito G en el conjunto X es regular si y sólo si | GRAMO | = | X  |. ^[11] El teorema de Cayley establece que cada grupo abstracto tiene una representación de permutación regular dada por el grupo que actúa sobre sí mismo (como un conjunto) mediante una multiplicación (derecha). A esto se le llama representación regular del grupo.

El grupo cíclico C ₆ en su representación regular contiene las seis permutaciones (primero se proporciona la forma unifilar de la permutación):

[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).

Así su índice de ciclo es:

${\displaystyle Z(C_{6})={\frac {1}{6}}\left(a_{1}^{6}+a_{2}^{3}+2a_{3}^{2}+2a_{6}\right).}$

A menudo, cuando un autor no desea utilizar la terminología de acción grupal, al grupo de permutación involucrado se le da 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 el grafo completo K ₃ 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. Cada permutación en el grupo S ₃ de permutaciones de vértice ( S ₃ en su acción natural, dada arriba) induce una permutación de arista. Estas son las permutaciones:

• La identidad: No se permutan vértices ni aristas; la contribución es ${\displaystyle a_{1}^{3}.}$
• Tres reflexiones en un eje que pasa por un vértice y el punto medio de la arista opuesta: Fijan una arista (la que no incide en el vértice) e intercambian las dos restantes; la contribución es ${\displaystyle 3a_{1}a_{2}.}$
• 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 ${\displaystyle 2a_{3}.}$

El índice de ciclo del grupo G de permutaciones de aristas inducidas por permutaciones de vértices de S ₃ es

${\displaystyle Z(G)={\frac {1}{6}}\left(a_{1}^{3}+3a_{1}a_{2}+2a_{3}\right).}$

Sucede que el gráfico completo K ₃ es isomorfo a su propio gráfico lineal (dual vértice-arista) y, por lo tanto, el grupo de permutación de aristas inducido por el grupo de permutación de vértices es el mismo que el grupo de permutación de vértices, es decir, S ₃ y el índice de ciclo es Z ( S3 ₎ . 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 vértices ( ). ${\displaystyle {\binom {n}{2}}}$ ${\displaystyle 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értice ( S ₄ en su acción natural) y las permutaciones de aristas ( S ₄ actuando sobre pares desordenados) que inducen:

• La identidad: esta permutación asigna todos los vértices (y por lo tanto, las aristas) a sí mismos y la contribución es ${\displaystyle a_{1}^{6}.}$
• Seis permutaciones que intercambian dos vértices: Estas permutaciones conservan la arista que conecta los dos vértices así como la arista que conecta los dos vértices no intercambiados. Los bordes restantes forman dos ciclos y la contribución es ${\displaystyle 6a_{1}^{2}a_{2}^{2}.}$
• 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, 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 ${\displaystyle 8a_{3}^{2}.}$
• Tres permutaciones que intercambian dos pares de vértices al mismo tiempo: Estas permutaciones conservan las dos aristas que conectan los dos pares. Los bordes restantes forman dos ciclos y la contribución es ${\displaystyle 3a_{1}^{2}a_{2}^{2}.}$
• Seis permutaciones que ciclan los vértices en un ciclo de cuatro: estas permutaciones crean un ciclo de cuatro aristas (aquellas que se encuentran en el ciclo) e intercambian las dos aristas restantes; la contribución es ${\displaystyle 6a_{2}a_{4}.}$

Podemos visualizar geométricamente los tipos de permutaciones 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 alrededor del 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 aristas opuestas.
• Seis reflexiones del rotor de 90 grados.

El índice de ciclo del grupo de permutación de aristas G de K ₄ es:

${\displaystyle Z(G)={\frac {1}{24}}\left(a_{1}^{6}+9a_{1}^{2}a_{2}^{2}+8a_{3}^{2}+6a_{2}a_{4}\right).}$

El índice de ciclo de las permutaciones de caras de un cubo.

Cubo con caras de colores.

Considere un cubo ordinario en tres espacios y su grupo de simetrías, llámelo C. Permuta las seis caras del cubo. (También podríamos considerar permutaciones de aristas o permutaciones de vértices). Hay veinticuatro simetrías.

• La identidad:

Existe una de esas permutaciones y su contribución es ${\displaystyle a_{1}^{6}.}$

• Seis rotaciones faciales de 90 grados:

Giramos sobre el eje que pasa por los centros de la cara y la cara opuesta. Esto arreglará la cara y la cara opuesta y creará un ciclo de cuatro caras paralelas al eje de rotación. La contribución es ${\displaystyle 6a_{1}^{2}a_{4}.}$

• Tres rotaciones faciales de 180 grados:

Giramos sobre el mismo eje que en el caso anterior, pero ahora no hay cuatro ciclos de las caras paralelas al eje, sino dos dos ciclos. La contribución es ${\displaystyle 3a_{1}^{2}a_{2}^{2}.}$

• Ocho rotaciones de vértice de 120 grados:

Esta vez giramos alrededor del eje que pasa por dos vértices opuestos (los extremos de una diagonal principal). Esto crea dos tres ciclos de caras (las caras que inciden en el mismo vértice forman un ciclo). La contribución es ${\displaystyle 8a_{3}^{2}.}$

• Seis rotaciones de borde de 180 grados:

Estas rotaciones de aristas giran alrededor del eje que pasa por los puntos medios de aristas opuestas que no inciden en la misma cara y paralelas entre sí e intercambian las dos caras que inciden en la primera arista, las dos caras que inciden en la segunda arista, y la dos caras que comparten dos vértices pero ninguna arista con las dos aristas, es decir, hay tres dos ciclos y la contribución es ${\displaystyle 6a_{2}^{3}.}$

La conclusión es que el índice de ciclo del grupo C es

${\displaystyle Z(C)={\frac {1}{24}}\left(a_{1}^{6}+6a_{1}^{2}a_{4}+3a_{1}^{2}a_{2}^{2}+8a_{3}^{2}+6a_{2}^{3}\right).}$

Índices de ciclo de algunos grupos de permutación.

Grupo de identidad E n

Este grupo contiene una permutación que fija cada elemento (debe ser una acción natural).

${\displaystyle Z(E_{n})=a_{1}^{n}.}$

Grupo cíclico C n

Un grupo cíclico , C _n , es el grupo de rotaciones de un n -gón 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 , que da el número de números naturales menores que d que son primos relativos de d . En la representación regular de C _n , una permutación de orden d tiene n / d ciclos de longitud d , así: ^[12]

${\displaystyle Z(C_{n})={\frac {1}{n}}\sum _{d|n}\varphi (d)a_{d}^{n/d}.}$

Grupo diédrico D n

El grupo diédrico es como el grupo cíclico , pero también incluye reflexiones. En su acción natural,

${\displaystyle Z(D_{n})={\frac {1}{2}}Z(C_{n})+{\begin{cases}{\frac {1}{2}}a_{1}a_{2}^{(n-1)/2},&n{\mbox{ odd, }}\\{\frac {1}{4}}\left(a_{1}^{2}a_{2}^{(n-2)/2}+a_{2}^{n/2}\right),&n{\mbox{ even.}}\end{cases}}}$

Grupo alterno A n

El índice de ciclo del grupo alterno en su acción natural como grupo de permutación es

${\displaystyle Z(A_{n})=\sum _{j_{1}+2j_{2}+3j_{3}+\cdots +nj_{n}=n}{\frac {1+(-1)^{j_{2}+j_{4}+\cdots }}{\prod _{k=1}^{n}k^{j_{k}}j_{k}!}}\prod _{k=1}^{n}a_{k}^{j_{k}}.}$

El numerador es 2 para las permutaciones pares y 0 para las permutaciones impares . El 2 es necesario porque . ${\displaystyle {\frac {1}{|A_{n}|}}={\frac {2}{n!}}}$

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:

${\displaystyle Z(S_{n})=\sum _{j_{1}+2j_{2}+3j_{3}+\cdots +nj_{n}=n}{\frac {1}{\prod _{k=1}^{n}k^{j_{k}}j_{k}!}}\prod _{k=1}^{n}a_{k}^{j_{k}}}$

que también se puede expresar en términos de polinomios de Bell completos :

${\displaystyle Z(S_{n})={\frac {B_{n}(0!\,a_{1},1!\,a_{2},\dots ,(n-1)!\,a_{n})}{n!}}.}$

Esta fórmula se obtiene contando cuántas veces puede ocurrir una forma de permutación determinada. Hay tres pasos: primero dividir el conjunto de n etiquetas en subconjuntos, donde hay subconjuntos de tamaño k . Cada uno de estos subconjuntos genera ciclos de longitud k . Pero no distinguimos entre ciclos del mismo tamaño, es decir, que se permutan por . Esto produce ${\displaystyle j_{k}}$ ${\displaystyle k!/k}$ ${\displaystyle S_{j_{k}}}$

${\displaystyle {\frac {n!}{\prod _{k=1}^{n}(k!)^{j_{k}}}}\prod _{k=1}^{n}\left({\frac {k!}{k}}\right)^{j_{k}}\prod _{k=1}^{n}{\frac {1}{j_{k}!}}={\frac {n!}{\prod _{k=1}^{n}k^{j_{k}}j_{k}!}}.}$

La fórmula se puede simplificar aún más si sumamos los índices de ciclo sobre cada , mientras usamos una variable adicional para realizar un seguimiento del tamaño total de los ciclos: ${\displaystyle n}$ ${\displaystyle y}$

${\displaystyle \sum \limits _{n\geq 1}y^{n}Z(S_{n})=\sum \limits _{n\geq 1}\sum _{j_{1}+2j_{2}+3j_{3}+\cdots +nj_{n}=n}\prod _{k=1}^{n}{\frac {a_{k}^{j_{k}}y^{kj_{k}}}{k^{j_{k}}j_{k}!}}=\prod \limits _{k\geq 1}\sum \limits _{j_{k}\geq 0}{\frac {(a_{k}y^{k})^{j_{k}}}{k^{j_{k}}j_{k}!}}=\prod \limits _{k\geq 1}\exp \left({\frac {a_{k}y^{k}}{k}}\right),}$

dando así una forma simplificada para el índice de ciclo de : ${\displaystyle S_{n}}$

${\displaystyle {\begin{aligned}Z(S_{n})&=[y^{n}]\prod \limits _{k\geq 1}\exp \left({\frac {a_{k}y^{k}}{k}}\right)\\&=[y^{n}]\exp \left(\sum \limits _{k\geq 1}{\frac {a_{k}y^{k}}{k}}\right).\end{aligned}}}$

Existe una fórmula recursiva útil para el índice de ciclo del grupo simétrico. Establezca y considere el tamaño l del ciclo que contiene n , donde hay formas de elegir los elementos restantes del ciclo y cada elección genera ciclos diferentes. ${\displaystyle Z(S_{0})=1}$ ${\displaystyle {\begin{matrix}1\leq l\leq n.\end{matrix}}}$ ${\textstyle {n-1 \choose l-1}}$ ${\displaystyle l-1}$ ${\displaystyle {\begin{matrix}{\frac {l!}{l}}=(l-1)!\end{matrix}}}$

Esto produce la recurrencia

${\displaystyle Z(S_{n})={\frac {1}{n!}}\sum _{g\in S_{n}}\prod _{k=1}^{n}a_{k}^{j_{k}(g)}={\frac {1}{n!}}\sum _{l=1}^{n}{n-1 \choose l-1}\;(l-1)!\;a_{l}\;(n-l)!\;Z(S_{n-l})}$

o

${\displaystyle Z(S_{n})={\frac {1}{n}}\sum _{l=1}^{n}a_{l}\;Z(S_{n-l}).}$

Aplicaciones

A lo largo de esta sección modificaremos ligeramente la notación de los índices de ciclo incluyendo explícitamente los nombres de las variables. Así, para el grupo de permutaciones G ahora escribiremos:

${\displaystyle Z(G)=Z(G;a_{1},a_{2},\ldots ,a_{n}).}$

Sea G 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 ₀ = F ₀ = 1. Tenemos: ^[13]

a) La función generadora ordinaria para f _k viene dada por:

${\displaystyle \sum _{k=0}^{n}f_{k}t^{k}=Z(G;1+t,1+t^{2},\ldots ,1+t^{n}),}$y

b) La función generadora exponencial para F _k viene dada por:

${\displaystyle \sum _{k=0}^{n}F_{k}t^{k}/k!=Z(G;1+t,1,1,\ldots ,1).}$

Sea G 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 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 No 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 combinatoria simbólica proporciona interpretaciones combinatorias de los resultados de estas operaciones formales.

La cuestión de cómo es 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

1. Dixon y Mortimer 1996, pág. 2, sección 1.2 Grupos simétricos
2. Cameron 1994, págs. 227-228
3. Cameron 1994, pág. 231, artículo 14.3
4. Este estilo de notación se encuentra con frecuencia en la literatura informática.
5. Las permutaciones cíclicas son funciones y el término producto realmente significa composición de estas funciones.
6. Hasta las diferentes formas en que se puede escribir un ciclo y el hecho de que los ciclos separados se conmutan para que puedan escribirse en cualquier orden.
7. Roberts y Tesman 2009, pág. 473
8. Técnicamente estamos usando la noción de equivalencia de acciones grupales, reemplazando G que actúa sobre las esquinas del cuadrado por la representación de permutación de G que actúa sobre X. A efectos de exposición, es mejor pasar por alto estos detalles.
9. Esta notación es común entre geómetras y combinatorias. Se utiliza en lugar del más común g(x) por razones tradicionales.
10. Existe una convención de no escribir los puntos fijos en la notación del ciclo para una permutación, pero deben representarse en el índice del ciclo.
11. Dixon y Mortimer 1996, pág. 9, Corolario 1.4A(iii)
12. van Lint y Wilson 1992, pág. 464, Ejemplo 35.1
13. Cameron 1994, pág. 248, Proposición 15.3.1
14. van Lint y Wilson 1992, pág. 463, Teorema 35.1

Referencias

• Brualdi, Richard A. (2010), "14. Pólya Counting", Combinatoria introductoria (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 grupal", Combinatoria: temas, técnicas, algoritmos , Cambridge: Cambridge University Press, págs. 245-256, ISBN 0-521-45761-0
• Dixon, John D.; Mortimer, Brian (1996), Grupos de permutación , Nueva York: Springer, ISBN 0-387-94599-7
• Roberts, Fred S.; Tesman, Barry (2009), "8.5 The Cycle Index", Combinatoria aplicada (2ª ed.), Boca Ratón: CRC Press, págs. 472–479, ISBN 978-1-4200-9982-9
• Tucker, Alan (1995), "9.3 The Cycle Index", Combinatoria aplicada (3.ª ed.), Nueva York: Wiley, págs. 365–371, ISBN 0-471-59504-7
• van Lint, JH; Wilson, RM (1992), "35.Pólya 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 cíclicos del operador set/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 .