El teorema de enumeración de Pólya , también conocido como el teorema de Redfield-Pólya y el conteo de Pólya , es un teorema en combinatoria que se deriva del lema de Burnside y, en última instancia, lo generaliza sobre el número de órbitas de una acción de grupo en un conjunto . El teorema fue publicado por primera vez por J. Howard Redfield en 1927. En 1937 fue redescubierto de forma independiente por George Pólya , quien luego popularizó enormemente el resultado aplicándolo a muchos problemas de conteo, en particular a la enumeración de compuestos químicos .
El teorema de enumeración de Pólya se ha incorporado a la combinatoria simbólica y la teoría de especies combinatorias .
Versión simplificada, no ponderada
Sea X un conjunto finito y sea G un grupo de permutaciones de X (o un grupo de simetría finito que actúa sobre X ). El conjunto X puede representar un conjunto finito de perlas y G puede ser un grupo elegido de permutaciones de las perlas. Por ejemplo, si X es un collar de n cuentas en un círculo, entonces la simetría rotacional es relevante, por lo que G es el grupo cíclico C n , mientras que si X es un brazalete de n cuentas en un círculo, las rotaciones y reflejos son relevantes, por lo que G es el grupo diedro D n de orden 2 n . Supongamos además que Y es un conjunto finito de colores, los colores de las cuentas, de modo que Y X es el conjunto de arreglos de colores de las cuentas (más formalmente: Y X es el conjunto de funciones .) A continuación, el grupo G actúa sobre Y X . El teorema de enumeración de Pólya cuenta el número de órbitas bajo G de arreglos coloreados de cuentas mediante la siguiente fórmula:
dónde es el número de colores y c ( g ) es el número de ciclos del grupo elemento g cuando se considera como una permutación de X .
Versión completa ponderada
En la versión más general e importante del teorema, los colores también se ponderan de una o más formas, y podría haber un número infinito de colores siempre que el conjunto de colores tenga una función generadora con coeficientes finitos. En el caso univariado, suponga que
es la función generadora del conjunto de colores, por lo que hay f w colores de peso w para cada entero w ≥ 0. En el caso multivariado, el peso de cada color es un vector de números enteros y hay una función generadora f ( t 1 , t 2 , ...) que tabula el número de colores con cada vector de pesos dado.
El teorema de enumeración emplea otra función generadora multivariante llamada índice de ciclo :
donde n es el número de elementos de X y c k ( g ) es el número de k -cycles del elemento de grupo g como una permutación de X .
Una disposición coloreada es una órbita de la acción de G en el conjunto Y X (donde Y es el conjunto de colores e Y X denota el conjunto de todas las funciones φ: X → Y ). El peso de tal disposición se define como la suma de los pesos de φ ( x ) sobre toda x en X . El teorema establece que la función generadora F del número de arreglos coloreados por peso viene dada por:
o en el caso multivariado:
Para reducir a la versión simplificada dada anteriormente, si hay m colores y todos tienen peso 0, entonces f ( t ) = m y
En la célebre aplicación de contar árboles (ver más abajo) y moléculas acíclicas, un arreglo de "cuentas de colores" es en realidad un arreglo de arreglos, como las ramas de un árbol enraizado. Así, la función generadora f para los colores se deriva de la función generadora F para los arreglos, y el teorema de enumeración de Pólya se convierte en una fórmula recursiva.
Ejemplos de
Collares y pulseras
Cubos de colores
¿De cuántas formas hay de colorear los lados de un cubo tridimensional con m colores, hasta la rotación del cubo? El grupo de rotación C del cubo actúa sobre los seis lados del cubo, que son equivalentes a cuentas. Su índice de ciclo es
que se obtiene analizando la acción de cada uno de los 24 elementos de C en los 6 lados del cubo, ver aquí los detalles.
Tomamos todos los colores para que tengan peso 0 y encontramos que hay
diferentes coloraciones.
Gráficos en tres y cuatro vértices
Un gráfico en m vértices se puede interpretar como una disposición de cuentas de colores. El conjunto X de "cuentas" es el conjunto debordes posibles, mientras que el conjunto de colores Y = {negro, blanco} corresponde a los bordes que están presentes (negro) o ausentes (blanco). El teorema de enumeración de Pólya se puede utilizar para calcular el número de gráficos hasta el isomorfismo con un número fijo de vértices, o la función generadora de estos gráficos según el número de aristas que tengan. Para este último propósito, podemos decir que un borde negro o presente tiene peso 1, mientras que un borde ausente o blanco tiene peso 0. Asíes la función generadora del conjunto de colores. El grupo de simetría relevante esel grupo simétrico en m letras. Este grupo actúa sobre el conjunto X de posibles aristas: una permutación φ convierte la arista {a, b} en la arista {φ (a), φ (b)}. Con estas definiciones, una clase de isomorfismo de grafos con m vértices es lo mismo que una órbita de la acción de G sobre el conjunto Y X de arreglos coloreados; el número de aristas del gráfico es igual al peso del arreglo.
Los ocho gráficos en tres vértices (antes de identificar los gráficos isomorfos) se muestran a la derecha. Hay cuatro clases de isomorfismos de gráficos, que también se muestran a la derecha.
El índice de ciclo del grupo S 3 que actúa sobre el conjunto de tres aristas es
(obtenido al inspeccionar la estructura del ciclo de la acción de los elementos del grupo; ver aquí ). Por lo tanto, de acuerdo con el teorema de enumeración, la función generadora de gráficos en 3 vértices hasta el isomorfismo es
que simplifica a
Por tanto, hay un gráfico cada uno con 0 a 3 aristas.
El índice de ciclo del grupo S 4 que actúa sobre el conjunto de 6 aristas es
(ver aquí ).
que simplifica a
Estos gráficos se muestran a la derecha.
Árboles ternarios enraizados
El conjunto T 3 de árboles ternarios enraizados consiste en árboles enraizados donde cada nodo (o vértice no foliar) tiene exactamente tres hijos (hojas o subárboles). Los árboles ternarios pequeños se muestran a la derecha. Tenga en cuenta que los árboles ternarios enraizados con n nodos son equivalentes a los árboles enraizados con n vértices de grado como máximo 3 (ignorando las hojas). En general, dos árboles enraizados son isomorfos cuando uno puede obtenerse del otro permutando los hijos de sus nodos. En otras palabras, el grupo que actúa sobre los hijos de un nodo es el grupo simétrico S 3 . Definimos el peso de un árbol ternario como el número de nodos (o vértices sin hojas).
Uno puede ver un árbol ternario enraizado como un objeto recursivo que es una hoja o un nodo con tres hijos que son árboles ternarios enraizados. Estos niños son equivalentes a cuentas; el índice de ciclo del grupo simétrico S 3 que actúa sobre ellos es
El teorema de enumeración de Polya traduce la estructura recursiva de árboles ternarios enraizados en una ecuación funcional para la función generadora F (t) de árboles ternarios enraizados por número de nodos. Esto se logra "coloreando" a los tres niños con árboles ternarios enraizados, ponderados por el número de nodo, de modo que la función generadora de color esté dada por que por el teorema de enumeración da
como función generadora para árboles ternarios enraizados, ponderado por uno menos que el número de nodo (ya que la suma de los pesos de los hijos no tiene en cuenta la raíz), de modo que
Esto es equivalente a la siguiente fórmula de recurrencia para el número t n de árboles ternarios enraizados con n nodos:
donde una , b y c son números enteros no negativos.
Los primeros valores de están
Prueba del teorema
La forma simplificada del teorema de enumeración de Pólya se deriva del lema de Burnside , que dice que el número de órbitas de los colorantes es el promedio del número de elementos defijado por la permutación g de G sobre todas las permutaciones g . La versión ponderada del teorema tiene esencialmente la misma demostración, pero con una forma refinada del lema de Burnside para la enumeración ponderada. Equivale a aplicar el lema de Burnside por separado a órbitas de diferente peso.
Para una notación más clara, deje ser las variables de la función generadora f de. Dado un vector de pesos, dejar denotar el término monomial correspondiente de f . Aplicar el lema de Burnside a las órbitas de peso, el número de órbitas de este peso es
dónde es el conjunto de colorantes de peso que también están fijados por g . Si luego sumamos todos los pesos posibles, obtenemos
Mientras tanto, un elemento de grupo g con estructura de ciclo contribuirá el término
con el índice de ciclo de G . El elemento g fija un elementosi y solo si la función φ es constante en cada ciclo q de g . Para cada ciclo q, la función generadora por peso de | q | colores idénticos del conjunto enumerado por f es
De ello se deduce que la función generadora por peso de los puntos fijados por g es el producto del término anterior sobre todos los ciclos de g , es decir
Sustituyendo esto en la suma de todo g, se obtiene el índice de ciclo sustituido como se afirma.
Ver también
Referencias
- Redfield, J. Howard (1927). "La teoría de las distribuciones reducidas por grupos". Revista Estadounidense de Matemáticas . 49 (3): 433–455. doi : 10.2307 / 2370675 . JSTOR 2370675 . Señor 1506633 .
- Frank Harary ; Ed Palmer (1967). "Los métodos de enumeración de Redfield". Revista Estadounidense de Matemáticas . 89 (2): 373–384. doi : 10.2307 / 2373127 . JSTOR 2373127 . Señor 0214487 .
- G. Pólya (1937). "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen" . Acta Mathematica . 68 (1): 145–254. doi : 10.1007 / BF02546665 .
- G. Pólya; RC Read (1987). Enumeración combinatoria de grupos, gráficos y compuestos químicos . Nueva York: Springer-Verlag . ISBN 0-387-96413-4. Señor 0884155 .
enlaces externos
- Aplicación del teorema de enumeración de Pólya-Burnside de Hector Zenil y Oleksandr Pavlyk, The Wolfram Demonstrations Project .
- Weisstein, Eric W. "Teorema de enumeración de Polya" . MathWorld .
- Frederic Chyzak Enumeración de alcoholes y otras clases de moléculas químicas, un ejemplo de la teoría de Pólya .