15.4: Teorema de Pólya

Antes de llegar a la versión completa de la fórmula de Pólya, debemos desarrollar una función generadora como se prometió al inicio del capítulo. Para ello, volveremos a nuestro ejemplo de la Sección 15.1.

15.4.1 El índice de ciclo

A diferencia de las funciones generadoras que encontramos en el Capítulo 8, las funciones generadoras que desarrollaremos en este capítulo tendrán más de una variable. Comenzamos asociando un monomio con cada elemento del grupo de permutación involucrado. En este caso, lo es\(D_8\), el grupo diedro de la plaza. Para determinar el monomio asociado a una permutación, necesitamos escribir la permutación en notación de ciclo y luego determinar el monomio en función del número de ciclos de cada longitud. Específicamente, si\(\pi\) es una permutación de\([n]\) con\(j_k\) ciclos de longitud\(k\) para\(1≤k≤n\), entonces el monomio asociado a\(\pi\) es\(x_1^{j_1}x_2^{j_2} \cdot \cdot \cdot x_n^{j_n}\). Tenga en cuenta que\(j_1+2j_2+3j_3+ \cdot \cdot \cdot +nj_n=n\). Por ejemplo, la permutación\(r_1=(1234)\) se asocia con el monomio\(x_4^1\) ya que consiste en un solo ciclo de longitud 4. La permutación\(r_2=(13)(24)\) tiene dos ciclos de longitud 2, y así su monomio es\(x_2^2\). Para\(p=(14)(2)(3)\), tenemos dos 1-ciclos y uno 2-ciclo, produciendo el monomio\(x_1^2x_2^1\). En la Figura 15.10, se muestran las ocho permutaciones\(D_8\) junto con sus monomios asociados.

Figura 15.10. Monomios derivados del grupo diedro de la plaza

Ahora veamos cómo se puede determinar el número de 2 colorantes del cuadrado fijado por una permutación a partir de su estructura de ciclo y monomio asociado. Si\(\pi(i)=j\), entonces sabemos que\(\pi\) para fijar una coloración\(C\), los vértices\(i\) y\(j\) deben ser coloreados igual en\(C\). Así, el segundo vértice de un ciclo debe tener el mismo color que el primero. Pero entonces el tercer vértice debe tener el mismo color que el segundo, que es el mismo color que el primero. De hecho, todos los vértices que aparecen en un ciclo de\(\pi\) deben tener el mismo color en\(C\) si π fija\(C!\) ya que estamos coloreando con los dos colores blanco y dorado, podemos elegir colorear los puntos de cada ciclo uniformemente blancos u dorados. Por ejemplo, para\(v=(12)(34)\) que la permutación fije una coloración del cuadrado, los vértices 1 y 2 deben ser coloreados del mismo color (2 opciones) y los vértices 3 y 4 deben ser coloreados del mismo color (2 opciones). Así, hay\(2 \cdot 2=4\) colorantes fijados por\(v\). Dado que hay dos opciones de cómo colorear uniformemente los elementos de un ciclo, dejando que\(x_i=2\) para todo i en el monomio asociado con\(\pi\) da el número de colorantes fijados por\(\pi\). En la Figura 15.10, la columna “Coloraciones fijas” da el número de 2 colorantes del cuadrado fijado por cada permutación. Antes, lo obtuvimos manualmente considerando la acción de\(D_8\) en el conjunto de los 16 colorantes. ¡Ahora solo necesitamos la notación de ciclo y los monomios que resultan de ella para derivar esto!

Recordemos que el Lema de Burnside afirma que el número de colorantes fijados por la acción de un grupo se puede obtener sumando el número fijado por cada permutación y dividiendo por el número de permutaciones en el grupo. Si hacemos eso en cambio para los monomios derivados de las permutaciones en un grupo de permutaciones\(G\) en el que cada ciclo de cada permutación tiene como máximo\(n\) entradas, obtenemos un polinomio conocido como índice de ciclo\(P_G(x_1,x_2,…,x_n)\). Para nuestro ejemplo de running, encontramos

\(P_{D_8}(x_1,x_2,x_3,x_4)=\dfrac{1}{8}(x_1^4+2x_1^2x_2^1+3x_2^2+2x_4^1)\).

Para encontrar el número de 2 colores distintos del cuadrado, así dejamos\(x_i=2\) para todos i y obtenemos\(P_{D_8}(2,2,2,2)=6\) como antes. Observe, sin embargo, que aquí tenemos algo más poderoso que el lema de Burnside. Podemos sustituir cualquier entero positivo\(m\) por cada uno\(x_i\) para averiguar cuántos\(m\) colores no equivalentes del cuadrado existen. Ya no tenemos que analizar cuántos colorantes corrige cada permutación. Por ejemplo,\(P_{D_8}(3,3,3,3)=21\), es decir, que 21 de los 81 colorantes de los vértices del cuadrado usando tres colores son distintos.

15.4.2 La fórmula de enumeración completa

Esperemos que se haga evidente el poder del índice de ciclo para contar colorantes que son distintos cuando se consideran simetrías. En la siguiente sección, proporcionaremos ejemplos adicionales de cómo se puede utilizar. No obstante, todavía no hemos visto todo el poder de la técnica de Pólya. Solo a partir del índice de ciclo, podemos determinar cuántos colorantes de los vértices del cuadrado son distintos. No obstante, ¿y si queremos saber cuántos de ellos tienen dos vértices blancos y dos vértices dorados? Aquí es donde la fórmula de enumeración de Pólya realmente juega el papel de una función generadora.

Consideremos nuevamente el índice de ciclo para el grupo diedro\(D_8\):

\(P_{D_8}(x_1,x_2,x_3,x_4)=\dfrac{1}{8}(x_1^4+2x_1^2x_2^1+3x_2^2+2x_4^1)\).

En lugar de sustituir enteros por el\(x_i\), consideremos qué sucede si sustituimos algo que nos permita rastrear los colores utilizados. Dado que\(x_1\) representa un ciclo de longitud 1 en una permutación, la elección del blanco u oro para el vértice en dicho ciclo equivale a un solo vértice que recibe ese color. ¿Qué pasa si\(w+g\) sustituimos? \(x_1\)? El primer término en\(P_{D_8}\) corresponde a la permutación de identidad\(ι\), que fija todos los colorantes del cuadrado. Dejar\(x_1=w+g\) en este término da

\((w+g)^4=g^4+4g^3w+6g^2w^2+4gw^3+w^4\),

que nos dice que\(ι\) fija una coloración con cuatro vértices dorados, cuatro coloraciones con tres vértices dorados y un vértice blanco, seis coloraciones con dos vértices dorados y dos vértices blancos, cuatro coloraciones con un vértice dorado y tres vértices blancos, y una coloración con cuatro vértices blancos.

Sigamos estableciendo un patrón aquí considerando la variable\(x_2\). Representa los ciclos de longitud 2 en una permutación. Dicho ciclo debe ser coloreado uniformemente blanco u oro para ser fijado por la permutación. Así, elegir blanco u oro para los vértices en ese ciclo da como resultado dos vértices blancos o dos vértices de oro en la coloración. Como esto sucede por cada ciclo de longitud 2, queremos\(w^2+g^2\) sustituirlo\(x_2\) en el índice de ciclo. Los\(x_1^2x_2^1\) términos en\(P_{D_8}\) están asociados con los volteretas\(p\) y\(n\). Dejando\(x_1=w+g\) y\(x_2=w^2+g^2\), encontramos

\(x_1^2x_2^1=g^4+2g^3w+2g^2w^2+2gw^3+w^4\),

de donde podemos deducir que p y n cada uno fijan una coloración con cuatro vértices dorados, dos colorantes con tres vértices dorados y un vértice blanco, y así sucesivamente. Al comparar esto con la Figura 15.2, se muestra que la función generadora está encendida.

A estas alturas el patrón se está haciendo evidente. Si\(w^i+g^i\) sustituimos\(x_i\) en el índice de ciclo para cada uno\(i\), entonces hacemos un seguimiento de cuántos vértices son de color blanco y cuántos son de color dorado. La simplificación del índice de ciclo en este caso es entonces una función generadora en la que el coeficiente on\(g^sw^t\) es el número de coloraciones distintas de los vértices del cuadrado con\(s\) vértices coloreados de oro y\(t\) vértices de color blanco. Hacer esto y simplificar da

\(P_{D_8}(w+g,w^2+g^2,w^3+g^3,w^4+g^4)=g^4+g^3w+2g^2w^2+gw^3+w^4\).

De esto encontramos una coloración con todos los vértices dorados, una coloración con todos los vértices blancos, una coloración con tres vértices dorados y un vértice blanco, una coloración con un vértice dorado y tres vértices blancos, y dos colorantes con dos vértices de cada color.

Al igual que con los otros resultados que hemos descubierto en este capítulo, esta propiedad del índice de ciclo se mantiene más allá del caso de colorear los vértices del cuadrado con dos colores. La versión completa es el teorema de enumeración de Pólya:

Teorema 15.11. Teorema de enumeración de Pólya

Dejar\(S\) ser un conjunto con\(|S|=r\) y\(\mathcal{C}\) el conjunto de colorantes de\(S\) usar los colores\(c_1,…,c_m\). Si un grupo de permutación\(G\) actúa\(S\) para inducir una relación de equivalencia sobre\(\mathcal{C}\), entonces

\(P_G ( \displaystyle \sum_{i=1}^m c_i, \sum_{i=1}^m c_i^2, \cdot \cdot \cdot, \sum_{i=1}^m c_i^r)\)

es la función generadora para el número de colorantes no equivalentes de\(S\) in\(\mathcal{C}\).

Si volvemos a colorear los vértices del cuadrado pero ahora permitimos el color azul también, encontramos

\(P_{D_8}(w+g+b,w^2+g^2+b^2,w^3+g^3+b^3,w^4+g^4+b^4)=b^4+b^3g+2b^2g^2+bg^3+g^4+b^3w+2b^2gw+2bg^2w+g^3w+2b^2w^2+2bgw^2+2g^2w^2+bw^3+gw^3+w^4\).

A partir de esta función generadora, podemos determinar fácilmente el número de colorantes no equivalentes con dos vértices azules, un vértice dorado y un vértice blanco para ser 2. Debido a que la función generadora del Teorema de Enumeración de Pólya registra el número de patrones no equivalentes, a veces se le llama el inventario de patrones.

¿Y si nos interesara hacer collares con 500 cuentas (muy pequeñas) de color blanco, dorado y azul? Esto equivaldría a colorear los vértices de un 500 gon regular, y el grupo diedro\(D_{1000}\) daría las transformaciones adecuadas. Con un sistema de álgebra computacional como Mathematica®, es posible producir rápidamente el inventario de patrones para tal problema. Al hacerlo, encontramos que hay

\(36360291795869936842385267079543319118023385026001623040346035832580600191583895484198508262979388783308179702534404046627287796430425271499270313565347234741708546745333417930824781980702852692187253642441292279756575936040804567103229 \approx 3.6 \times 10^{235}\)

posibles collares. De ellos,

\(252949184234046077349041318620101048779141729407880866280363896567824471388337043268753932294423230859058382000714795759057317766605088026968640797415175535033372572682057214340157297357996345021733060 \approx 2.5 \times 10^{200}\)

tienen 225 cuentas blancas, 225 cuentas de oro y 50 cuentas azules.

El resto de este capítulo se centrará en las aplicaciones del Teorema de Enumeración de Pólya y el inventario de patrones en una variedad de entornos.