Teorema de enumeración de Pólya

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 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 grupal 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 a la teoría de especies combinatorias.

Versión simplificada y 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 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, por lo 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 reflexiones son relevantes, por lo que G es el grupo diédrico 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 disposiciones coloreadas de cuentas (más formalmente: Y ^X es el conjunto de funciones ${\displaystyle X\to Y}$ .) 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 \left|Y^{X}/G\right|={\frac {1}{|G|}}\sum _{g\in G}m^{c(g)}}$

dónde ${\displaystyle m=|Y|}$ 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.

Versión completa y ponderada

En la versión más general e 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 de pesos dado.

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 tal disposición se define como la suma de los pesos de φ( x ) sobre todo x en X. El teorema establece que la función generadora F del número de disposiciones de colores en peso viene 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 proporcionada 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 célebre aplicación de contar árboles (ver más abajo) y 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 enraizado. Así, 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

¿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 equivalen 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)}$

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

Tomamos todos los colores para que tengan 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.

Gráficas de tres y cuatro vértices.

Una gráfica de m vértices se puede interpretar como una disposición de cuentas de colores. El conjunto X de "cuentas" es el conjunto de ${\displaystyle {\binom {m}{2}}}$ aristas posibles, mientras que el conjunto de colores Y = {negro, blanco} corresponde a aristas 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 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 un borde negro o presente tiene peso 1, mientras que un borde ausente o blanco tiene peso 0. De este modo ${\displaystyle f(t)=1+t}$ es la función generadora del conjunto de colores. El grupo de simetría relevante es ${\displaystyle G=S_{m},}$ el 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 gráficos con m vértices es lo mismo que una órbita de la acción de G sobre el conjunto Y ^X de disposiciones coloreadas; el número de aristas del gráfico es igual al peso de la disposición.

Todos los gráficos en tres vértices.

Gráficos no isomorfos en tres vértices.

Los ocho gráficos en tres vértices (antes de identificar los gráficos isomórficos) se muestran a la derecha. Hay cuatro clases de gráficos de isomorfismo, 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 inspeccionando la estructura del ciclo de acción de los elementos del grupo). Así, según el teorema de enumeración, la función generadora de gráficos 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 que simplifica a

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

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

Clases de isomorfismo de gráficos 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 que 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₃ de árboles ternarios enraizados consta de árboles enraizados donde cada nodo (o vértice que no es hoja) tiene exactamente tres hijos (hojas o subárboles). A la derecha se muestran pequeños árboles ternarios. Tenga en cuenta que los árboles ternarios enraizados con n nodos son equivalentes a á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₃. Definimos el peso de dicho árbol ternario como el número de nodos (o vértices que no son hojas).

Archivo:TernaryTrees.png

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

Se puede ver 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 niños equivalen 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 á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" los tres hijos con árboles ternarios enraizados, ponderados por el número de nodo, de modo que la función generadora de color esté dada por ${\displaystyle f(t)=F(t)}$ que por el teorema de enumeración da

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

como función generadora para árboles ternarios enraizados, ponderada por uno menos que el número de nodo (ya que la suma de los pesos secundarios 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 equivale 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 ${\displaystyle t_{n}}$ son

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

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 de ${\displaystyle Y^{X}}$ fijado por la permutación g de G sobre todas las permutaciones g. La versión ponderada del teorema tiene esencialmente la misma prueba, pero con una forma refinada del lema de Burnside para enumeración ponderada. Es equivalente a aplicar el lema de Burnside por separado a órbitas de diferente peso.

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

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

dónde ${\displaystyle (Y^{X})_{\omega ,g}}$ es el conjunto de colorantes de peso ${\displaystyle \omega }$ que también están fijados por g. Si luego sumamos todos los pesos posibles, obtenemos

${\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 de ciclo ${\displaystyle j_{1}(g),j_{2}(g),\ldots ,j_{n}(g)}$ contribuirá el término

${\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. ${\displaystyle \phi \in Y^{X}}$sí y solo si la función φ es constante en cada ciclo q de g. Para cada ciclo q, la función generadora en peso de | q | colores idénticos del conjunto enumerado por f es

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

De ello se deduce que la función generadora en 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). «The Theory of Group-Reduced Distributions». American Journal of Mathematics 49 (3): 433-455. doi:10.2307/2370675. 
• Frank Harary; Ed Palmer (1967). «The Enumeration Methods of Redfield». American Journal of Mathematics 89 (2): 373-384. doi:10.2307/2373127. 
• 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; R. C. Read (1987). Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds. New York: Springer-Verlag. ISBN 0-387-96413-4. 

Enlaces externos

• Aplicación del teorema de enumeración de Pólya-Burnside de Hector Zenil y Oleksandr Pavlyk, The Wolfram Demonstrations Project.