Í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 la enumeración combinatoria .

Cada permutación π de un conjunto finito de objetos divide ese conjunto en ciclos ; el monomio de índice de ciclo de π es un monomio en las 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 permutación 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 de índice de ciclo de un grupo de permutación, se pueden enumerar las clases de equivalencia debidas a la acción del grupo . Este es el ingrediente principal del teorema de enumeración de Pólya . La realización de operaciones algebraicas y diferenciales formales sobre estos polinomios y la posterior interpretación de los resultados de forma combinatoria constituyen el núcleo de la teoría de especies .

Grupos de permutación y acciones grupales

Una función biyectiva de un conjunto X sobre sí misma se denomina permutación de X , y el conjunto de todas las permutaciones de X forma un grupo bajo la composición de funciones, denominado 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 en 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 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 las aplicaciones combinatorias, el interés está en el conjunto X ; por ejemplo, contar cosas en X y saber qué estructuras podrían quedar invariantes 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, se trabaja con una representación de permutación del grupo 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 preocupados por los núcleos de las acciones de grupo, que miden cuánto se pierde al pasar del grupo a su representación de permutación. ^[3]

Representación de permutaciones mediante ciclos disjuntos

Las permutaciones finitas se representan con mayor frecuencia como acciones de grupo en el conjunto X = {1,2, ..., n }. Una permutación en este contexto se puede representar mediante una notación de dos líneas. Por lo tanto,

${\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 a partir de las columnas de la 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 una permutación cíclica porque "recorre" los números, y una tercera notación para ello sería (1 2 3 4 5). Esta notación cíclica se debe leer como: cada elemento se envía al elemento de su derecha, pero el último elemento se envía al primero ("recorre" hasta el principio). Con la notación de ciclos, 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 longitud de un ciclo es la cantidad de elementos que lo componen.

No todas las permutaciones son cíclicas, pero cada una de ellas puede escribirse como un producto ^[5] de ciclos disjuntos (que no tienen ningún elemento en común) de una manera, básicamente. ^[6] Como una permutación puede tener puntos fijos (elementos que no cambian con la permutación), estos se representarán mediante 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 , 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 longitud de ciclo distinta de los ciclos que aparecen en la descomposición en ciclos de la permutación. En el ejemplo anterior había tres longitudes de ciclo diferentes, por lo que utilizaremos tres variables, a ₁ , a ₂ y a ₃ (en general, utilizaremos la variable a _k para que corresponda a los ciclos de longitud k ). 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 en ciclos de la permutación g . Podemos entonces asociar el monomio de índice de 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 a ₁ a ₂ ² a ₄ ² .

Definición

El índice de ciclo de un grupo de permutación G es el promedio de los monomios de í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 longitud de un ciclo c denotada por | c  |.

Sea ahora 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

Consideremos 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 sólo las esquinas del cuadrado. Al etiquetar estas esquinas como 1, 2, 3 y 4 (yendo 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 consiste en 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. Nótese 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 ₄ , y esta representación de permutación es su representación regular . Los monomios de índice de ciclo son a ₄ , a ₂ ² , a ₄ y a ₁ ⁴ respectivamente. Por lo 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 no ordenados 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 es ahora { 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 diagonales del cuadrado o, en un contexto completamente diferente, como las aristas del grafo 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 manera natural. Cualquier permutación g enviaría ( x , y ) → ( x ^g , y ^g ) (en este caso también tendríamos pares ordenados 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 de ciclo depende de la acción del grupo y no del grupo abstracto. Dado que existen muchas representaciones de permutación de un grupo abstracto, es útil contar con cierta terminología para distinguirlas.

Cuando un grupo abstracto se define en términos de permutaciones, se trata de un grupo de permutaciones y la acción del grupo es el homomorfismo identidad . Esto se denomina 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 por lo tanto 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 permutaciones 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 transitivo 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 permutación transitiva finito G en el conjunto X es regular si y solo si | G | = | 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) por multiplicación (derecha). Esto se llama la representación regular del grupo.

El grupo cíclico C ₆ en su representación regular contiene las seis permutaciones (primero se da 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).

Por lo tanto 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, se le asigna al grupo de permutación involucrado un nombre que implica cuál es la acción. Los tres ejemplos siguientes ilustran este punto.

El índice de ciclo de lagrupo de permutación de aristasdel 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 utilizar el lenguaje geométrico para describir las permutaciones involucradas como simetrías del triángulo. Toda permutación en el grupo S ₃ de permutaciones de vértices ( S ₃ en su acción natural, dada anteriormente) induce una permutación de aristas. Éstas 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: Éstas 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 otra en el sentido contrario: 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 grafo completo K ₃ es isomorfo a su propio grafo 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 ( S ₃ ). Este no es el caso de los grafos 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 tres vértices. Éstas son las permutaciones de vértices ( S ₄ en su acción natural) y las permutaciones de aristas ( S ₄ actuando sobre pares no ordenados) que inducen:

• La identidad: Esta permutación asigna todos los vértices (y, por lo tanto, los bordes) 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. Las aristas restantes forman dos ciclos de dos y la contribución es ${\displaystyle 6a_{1}^{2}a_{2}^{2}.}$
• Ocho permutaciones que fijan un vértice y producen un triciclo para los tres vértices no fijados: Estas permutaciones crean dos triciclos de aristas, una que contiene aquellas que no inciden en el vértice y otra que contiene aquellas 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. Las aristas restantes forman dos ciclos de dos y la contribución es ${\displaystyle 3a_{1}^{2}a_{2}^{2}.}$
• 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 ${\displaystyle 6a_{2}a_{4}.}$

Podemos visualizar los tipos de permutaciones geométricamente como simetrías de un tetraedro regular . Esto nos lleva a la siguiente descripción de los tipos de permutaciones.

• 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 sobre el eje que une los puntos medios de dos aristas opuestas.
• Seis rotorreflexiones 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 las caras de un cubo

Cubo con caras de colores

Consideremos un cubo ordinario en el espacio tridimensional y su grupo de simetrías, llamémoslo 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 de cara de 90 grados:

Giramos sobre el eje que pasa por los centros de la cara y la cara opuesta. 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 ${\displaystyle 6a_{1}^{2}a_{4}.}$

• Tres rotaciones de cara 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 ciclos de dos. La contribución es ${\displaystyle 3a_{1}^{2}a_{2}^{2}.}$

• Ocho rotaciones de vértice de 120 grados:

Esta vez giramos sobre el eje que pasa por dos vértices opuestos (los puntos finales de una diagonal principal). Esto crea dos triciclos 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 sobre el eje que pasa por los puntos medios de aristas opuestas no incidentes en la misma cara y paralelas entre sí e intercambian las dos caras que inciden en la primera arista, las dos caras incidentes en la segunda arista y las 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 identidadminorte

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

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

Grupo cíclicodonorte

Un grupo cíclico , C _n es el grupo de rotaciones de un n -gono 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 entre sí con d . En la representación regular de C _n , una permutación de orden d tiene n / d ciclos de longitud d , por lo tanto: ^[12]

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

Grupo diedroDnorte

El grupo diedro 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 alternoAnorte

El índice de ciclo del grupo alternante 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étricoSnorte

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}}}$

Esto también puede expresarse 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 dada. Hay tres pasos: primero, se divide 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, 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 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 una de esas elecciones 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 ciclos incluyendo explícitamente los nombres de las variables. Así, para el grupo de permutación G escribiremos ahora:

${\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 (véase #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 está 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 está 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 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 desprende del lema de conteo de órbitas (también conocido como el 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 de varias variables y los resultados anteriores muestran que ciertas evaluaciones de este polinomio dan resultados combinatoriamente significativos. Como polinomios, también pueden sumarse, restarse, diferenciarse e integrarse formalmente . El área de 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 permutaciones aleatorias .

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, sección 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 disjuntos conmutan, por lo que pueden escribirse en cualquier orden.
7. Roberts y Tesman 2009, pág. 473
8. Técnicamente, utilizamos la noción de equivalencia de acciones grupales, reemplazando G actuando sobre las esquinas del cuadrado por la representación de permutación de G actuando sobre X. Para fines de exposición, es mejor pasar por alto estos detalles.
9. Esta notación es común entre geómetras y combinatorios. Se utiliza en lugar de la más común g(x) por razones tradicionales.
10. Existe una convención para no escribir los puntos fijos en la notación de ciclo para una permutación, pero estos deben representarse en el índice del ciclo.
11. Dixon y Mortimer 1996, pág. 9, Corolario 1.4A(iii)
12. van Lint & Wilson 1992, pág. 464, Ejemplo 35.1
13. Cameron 1994, pág. 248, Proposición 15.3.1
14. van Lint & Wilson 1992, pág. 463, Teorema 35.1

Referencias

• Brualdi, Richard A. (2010), "14. Pólya Counting", Introductory Combinatorics (5.ª ed.), Upper Saddle River, NJ: 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 El índice del ciclo", Applied Combinatorics (2.ª ed.), Boca Raton: CRC Press, págs. 472–479, ISBN 978-1-4200-9982-9
• Tucker, Alan (1995), "9.3 El índice de ciclo", Applied Combinatorics (3.ª ed.), Nueva York: Wiley, págs. 365–371, ISBN 0-471-59504-7
• van Lint, JH; Wilson, RM (1992), "35. Teoría de conteo de Pólya", 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/multiconjunto 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 .