Teorema de enumeración de Pólya

Fórmula para el número de órbitas de una acción grupal

El teorema de enumeración de Pólya , también conocido como teorema de Redfield–Pólya y conteo de Pólya , es un teorema de combinatoria que se deduce y, en última instancia, generaliza el lema de Burnside 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 independientemente por George Pólya , quien luego popularizó enormemente el resultado al aplicarlo 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 a la teoría de especies combinatorias .

Versión simplificada y sin ponderación

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 cuentas, y G puede ser un grupo elegido de permutaciones de las cuentas. Por ejemplo, si X es un collar de n cuentas en un círculo, entonces la simetría rotacional es relevante, de modo que G es el grupo cíclico C _n , mientras que si X es una pulsera de n cuentas en un círculo, las rotaciones y las reflexiones son relevantes, de modo que G es el grupo diedro D _n de orden 2 n . Supóngase además que Y es un conjunto finito de colores —los colores de las cuentas— de modo que Y ^X es el conjunto de disposiciones coloreadas de cuentas (más formalmente: Y ^X es el conjunto de funciones ). Entonces 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 disposiciones coloreadas de cuentas mediante la siguiente fórmula: ${\displaystyle X\to Y}$

${\displaystyle \left|Y^{X}/G\right|={\frac {1}{|G|}}\sum _{g\in G}m^{c(g)}}$

donde es el número de colores y c ( g ) es el número de ciclos del elemento del grupo g cuando se considera como una permutación de X . ${\displaystyle m=|Y|}$

Versión completa y ponderada

En la versión más general y más importante del teorema, los colores también se ponderan de una o más maneras, 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, supongamos que

${\displaystyle f(t)=f_{0}+f_{1}t+f_{2}t^{2}+\cdots }$

es la función generadora del conjunto de colores, de modo que existen 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 existe una función generadora f ( t ₁ , t ₂ , ...) que tabula el número de colores con cada vector dado de pesos.

El teorema de enumeración emplea otra función generadora multivariante llamada índice de ciclo :

${\displaystyle Z_{G}(t_{1},t_{2},\ldots ,t_{n})={\frac {1}{|G|}}\sum _{g\in G}t_{1}^{c_{1}(g)}t_{2}^{c_{2}(g)}\cdots t_{n}^{c_{n}(g)}}$

donde n es el número de elementos de X y c _k ( g ) es el número de k -ciclos del elemento del grupo g como una permutación de X .

Una disposición coloreada es una órbita de la acción de G sobre 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 dicha disposición se define como la suma de los pesos de φ( x ) sobre todos los x en X . El teorema establece que la función generadora F del número de disposiciones coloreadas por peso está dada por:

${\displaystyle F(t)=Z_{G}(f(t),f(t^{2}),f(t^{3}),\ldots ,f(t^{n}))}$

o en el caso multivariado:

${\displaystyle F(t_{1},t_{2},\ldots )=Z_{G}(f(t_{1},t_{2},\ldots ),f(t_{1}^{2},t_{2}^{2},\ldots ),f(t_{1}^{3},t_{2}^{3},\ldots ),\ldots ,f(t_{1}^{n},t_{2}^{n},\ldots )).}$

Para reducir a la versión simplificada dada anteriormente, si hay m colores y todos tienen peso 0, entonces f ( t ) =  m y

${\displaystyle \left|Y^{X}/G\right|=F(0)=Z_{G}(m,m,\ldots ,m)={\frac {1}{|G|}}\sum _{g\in G}m^{c(g)}.}$

En la famosa aplicación de los árboles de conteo (ver más abajo) y las moléculas acíclicas, una disposición de "cuentas de colores" es en realidad una disposición de disposiciones, como las ramas de un árbol con raíces. Por lo tanto, la función generadora f para los colores se deriva de la función generadora F para las disposiciones, y el teorema de enumeración de Pólya se convierte en una fórmula recursiva.

Ejemplos

Collares y pulseras

Cubos de colores

¿De cuántas maneras se pueden colorear los lados de un cubo tridimensional con m colores, hasta que se gira el 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

${\displaystyle Z_{C}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{24}}\left(t_{1}^{6}+6t_{1}^{2}t_{4}+3t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}^{3}\right)}$

que se obtiene analizando la acción de cada uno de los 24 elementos de C sobre las 6 caras del cubo, ver aquí para los detalles.

Consideramos que todos los colores tienen peso 0 y encontramos que hay

${\displaystyle F(0)=Z_{C}(m,m,m,m)={\frac {1}{24}}\left(m^{6}+3m^{4}+12m^{3}+8m^{2}\right)}$

Diferentes coloraciones.

Grafos de tres y cuatro vértices

Un grafo de m vértices puede interpretarse como una disposición de cuentas de colores. El conjunto X de "cuentas" es el conjunto de aristas posibles, mientras que el conjunto de colores Y = {negro, blanco} corresponde a las aristas presentes (negras) o ausentes (blancas). El teorema de enumeración de Pólya puede utilizarse para calcular el número de grafos hasta el isomorfismo con un número fijo de vértices, o la función generadora de estos grafos según el número de aristas que tengan. Para este último propósito, podemos decir que una arista negra o presente tiene peso 1, mientras que una arista ausente o blanca tiene peso 0. Así pues, es la función generadora para el conjunto de colores. El grupo de simetría relevante es el grupo simétrico de m letras. Este grupo actúa sobre el conjunto X de aristas posibles: 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 grafo es igual al peso del arreglo. ${\displaystyle {\binom {m}{2}}}$ ${\displaystyle f(t)=1+t}$ ${\displaystyle G=S_{m},}$

Todos los gráficos en tres vértices

Grafos no isomorfos en tres vértices

A la derecha se muestran los ocho grafos con tres vértices (antes de identificar los grafos isomorfos). Hay cuatro clases de grafos isomorfos, que también se muestran a la derecha.

El índice de ciclo del grupo S ₃ que actúa sobre el conjunto de tres aristas es

${\displaystyle Z_{G}(t_{1},t_{2},t_{3})={\frac {1}{6}}\left(t_{1}^{3}+3t_{1}t_{2}+2t_{3}\right)}$

(obtenido al inspeccionar la estructura cíclica de la acción de los elementos del grupo; ver aquí ). Por lo tanto, según el teorema de enumeración, la función generadora de grafos en 3 vértices hasta el isomorfismo es

${\displaystyle F(t)=Z_{G}\left(t+1,t^{2}+1,t^{3}+1\right)={\frac {1}{6}}\left((t+1)^{3}+3(t+1)(t^{2}+1)+2(t^{3}+1)\right),}$

Lo cual se simplifica a

${\displaystyle F(t)=t^{3}+t^{2}+t+1.}$

Por lo tanto, hay un gráfico cada uno con entre 0 y 3 aristas.

Clases de isomorfismo de grafos en cuatro vértices.

El índice de ciclo del grupo S ₄ que actúa sobre el conjunto de 6 aristas es

${\displaystyle Z_{G}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{24}}\left(t_{1}^{6}+9t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}t_{4}\right)}$

(ver aquí .) Por lo tanto

${\displaystyle F(t)=Z_{G}\left(t+1,t^{2}+1,t^{3}+1,t^{4}+1\right)={\frac {(t+1)^{6}+9(t+1)^{2}(t^{2}+1)^{2}+8(t^{3}+1)^{2}+6(t^{2}+1)(t^{4}+1)}{24}}}$

Lo cual se simplifica a

${\displaystyle F(t)=t^{6}+t^{5}+2t^{4}+3t^{3}+2t^{2}+t+1.}$

Estos gráficos se muestran a la derecha.

Árboles ternarios enraizados

El conjunto T _{3 de} árboles ternarios con raíz consiste en árboles con raíz donde cada nodo (o vértice no hoja) tiene exactamente tres hijos (hojas o subárboles). A la derecha se muestran árboles ternarios pequeños. Nótese que los árboles ternarios con raíz con n nodos son equivalentes a los árboles con raíz con n vértices de grado 3 como máximo (ignorando las hojas). En general, dos árboles con raíz 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 ₃ . Definimos el peso de un árbol ternario de este tipo como el número de nodos (o vértices no hojas).

Árboles ternarios con raíz en 0, 1, 2, 3 y 4 nodos (=vértices que no son hojas). La raíz se muestra en azul, las hojas no se muestran. Cada nodo tiene tantas hojas como para que el número de sus hijos sea igual a 3.

Se puede considerar un árbol ternario enraizado como un objeto recursivo que es una hoja o un nodo con tres hijos que son a su vez árboles ternarios enraizados. Estos hijos son equivalentes a cuentas; el índice de ciclo del grupo simétrico S ₃ que actúa sobre ellos es

${\displaystyle Z_{S_{3}}(t_{1},t_{2},t_{3})={\frac {t_{1}^{3}+3t_{1}t_{2}+2t_{3}}{6}}.}$

El teorema de enumeración de Polya traduce la estructura recursiva de los árboles ternarios con raíz en una ecuación funcional para la función generadora F(t) de árboles ternarios con raíz por número de nodos. Esto se logra "coloreando" los tres hijos con árboles ternarios con raíz, ponderados por número de nodo, de modo que la función generadora de color esté dada por lo que por el teorema de enumeración da ${\displaystyle f(t)=F(t)}$

${\displaystyle {\frac {F(t)^{3}+3F(t)F(t^{2})+2F(t^{3})}{6}}}$

como función generadora de árboles ternarios enraizados, ponderada 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

${\displaystyle F(t)=1+t\cdot {\frac {F(t)^{3}+3F(t)F(t^{2})+2F(t^{3})}{6}}.}$

Esto es equivalente a la siguiente fórmula de recurrencia para el número t _n de árboles ternarios enraizados con n nodos:

${\displaystyle {\begin{aligned}t_{0}&=1\\t_{n+1}&={\frac {1}{6}}\left(\sum _{a+b+c=n}t_{a}t_{b}t_{c}+3\sum _{a+2b=n}t_{a}t_{b}+2\sum _{3a=n}t_{a}\right)\end{aligned}}}$

donde a , b y c son números enteros no negativos.

Los primeros valores de son ${\displaystyle t_{n}}$

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 (secuencia A000598 en la OEIS ).

Prueba del teorema

La forma simplificada del teorema de enumeración de Pólya se desprende del lema de Burnside , que dice que el número de órbitas de coloraciones es el promedio del número de elementos de fijados 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. Es equivalente a aplicar el lema de Burnside por separado a órbitas de diferente peso. ${\displaystyle Y^{X}}$

Para una notación más clara, sean las variables de la función generadora f de . Dado un vector de pesos , sea el término monomial correspondiente de f . Aplicando el lema de Burnside a las órbitas de peso , el número de órbitas de este peso es ${\displaystyle x_{1},x_{2},\ldots }$ ${\displaystyle Y}$ ${\displaystyle \omega }$ ${\displaystyle x^{\omega }}$ ${\displaystyle \omega }$

${\displaystyle {\frac {1}{|G|}}\sum _{g\in G}\left|(Y^{X})_{\omega ,g}\right|}$

donde es el conjunto de coloraciones de peso que también están fijadas por g . Si sumamos todos los pesos posibles, obtenemos ${\displaystyle (Y^{X})_{\omega ,g}}$ ${\displaystyle \omega }$

${\displaystyle F(x_{1},x_{2},\ldots )={\frac {1}{|G|}}\sum _{g\in G,\omega }x^{\omega }\left|(Y^{X})_{\omega ,g}\right|.}$

Mientras tanto, un elemento de grupo g con estructura cíclica aportará el término ${\displaystyle j_{1}(g),j_{2}(g),\ldots ,j_{n}(g)}$

${\displaystyle t_{1}^{j_{1}(g)}t_{2}^{j_{2}(g)}\cdots t_{n}^{j_{n}(g)}}$

al índice de ciclo de G . El elemento g fija un elemento si y sólo 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 ${\displaystyle \phi \in Y^{X}}$

${\displaystyle f\left(x_{1}^{|q|},x_{2}^{|q|},x_{3}^{|q|},\ldots \right).}$

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

${\displaystyle {\begin{aligned}\sum _{\omega }x^{\omega }\left|(Y^{X})_{\omega ,g}\right|&=\prod _{q{\text{ cycle of }}g}f\left(x_{1}^{|q|},x_{2}^{|q|},x_{3}^{|q|},\ldots \right)\\&=f(x_{1},x_{2},\ldots )^{j_{1}(g)}f\left(x_{1}^{2},x_{2}^{2},\ldots \right)^{j_{2}(g)}\cdots f\left(x_{1}^{n},x_{2}^{n},\ldots \right)^{j_{n}(g)}\end{aligned}}}$

Sustituyendo esto en la suma de todos los g se obtiene el índice de ciclo sustituido como se afirma.

Véase también

• Teorema de enumeración etiquetado

Referencias

• Redfield, J. Howard (1927). "La teoría de distribuciones reducidas por grupos". American Journal of Mathematics . 49 (3): 433–455. doi :10.2307/2370675. JSTOR  2370675. MR  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. MR  0214487.
• G. Pólya (1937). "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen". Acta Matemática . 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.Sr. 0884155  .

Enlaces externos

• Aplicación del teorema de enumeración de Pólya-Burnside por 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.