15.5: Aplicaciones de la fórmula de enumeración de Pólya

Esta sección explora una serie de situaciones en las que se puede utilizar la fórmula de enumeración de Pólya. Las aplicaciones provienen de una variedad de dominios y están dispuestas en orden creciente de complejidad, comenzando con un ejemplo de la teoría musical y concluyendo con contar gráficas no isomórficas.

15.5.1 Balanzas musicales de conteo

La música occidental generalmente se basa en un sistema de 12 notas equidistantes. Si bien estas notas suelen ser nombradas por letras del alfabeto (con modificadores), para nuestros fines bastará numerarlas como 0,1,... ,11. Estas notas están dispuestas en octavas para que el siguiente tono después de 11 se llame nuevamente 0 y el tono antes de 0 se llame 11. Por esta razón, podemos considerar que el sistema de notas corresponde a los enteros módulo 12. Con estas definiciones, una escala es un subconjunto de {0,1,... ,11} dispuestos en orden creciente. Una transposición de una escala es una transformación uniforme que reemplaza cada nota x de la escala por\(x+a(mod12)\) para alguna constante\(a\). Los músicos consideran que dos escalas son equivalentes si una es una transposición de la otra. Dado que una escala es un subconjunto, tampoco se paga consideración a qué nota inicia la escala. La pregunta que investigamos en esta sección es “¿Cuántas escalas no equivalentes hay que consisten precisamente en\(k\) notas?”

Debido a la naturaleza cíclica de los nombres de las notas, podemos considerar ordenarlos en orden de las agujas del reloj alrededor de un círculo. Seleccionar las notas para una escala se convierte entonces en un problema de coloración si decimos que las notas seleccionadas son de color negro y las notas no seleccionadas son de color blanco. En la Figura 15.12, mostramos tres escalas de 5 notas utilizando esta convención. Observe que ya que se\(S_2\) pueden obtener de\(S_1\) girándolo hacia adelante siete posiciones,\(S_1\) y\(S_2\) son equivalentes por la transposición de sumar 7. Sin embargo, no\(S_3\) es equivalente\(S_1\) o\(S_2\), ya que no se puede obtener de ellos por rotación. (Tenga en cuenta que\(S_3\) podría obtenerse de\(S_1\) si permitimos volteretas además de rotaciones. Ya que la única operación permitida es la transposición, que corresponde a rotación, son inequivalentes.)

Figura 15.12. Tres escalas representadas por coloración

Ahora hemos modelado matemáticamente escalas musicales como estructuras discretas de una manera que podemos usar el Teorema de Enumeración de Pólya. ¿Cuál es el grupo que actúa sobre nuestros colorantes negro/blanco de los vértices de un 12-gon regular? Una permutación en el grupo es\(τ=(0 1 2 3 4 5 6 7 8 9 10 11)\), que corresponde a la transposición por una nota. De hecho, cada elemento del grupo se puede realizar como alguna potencia de\(τ\) ya que solo se permiten rotaciones y\(τ\) es la rotación más pequeña posible. Así, el grupo que actúa sobre los colorantes es el grupo cíclico de orden 12, denotado\(C_{12}=\{ι,τ,τ^2,…,τ^{11}\}\). El ejercicio 15.6.5 te pide que escribas todos los elementos de este grupo en notación de ciclo. La mejor manera de hacerlo es multiplicando\(τ^{i−1}\) por τ (es decir, computar\(ττ^{i−1}\)) para encontrar\(τ\). Una vez que hayas hecho esto, podrás verificar fácilmente que el índice de ciclo es

\(P_{C_{12}}(x_1,...,x_{12}) = \dfrac{x_1^{12}}{12} + \dfrac{x_2^6}{12} + \dfrac{x_3^4}{6} + \dfrac{x_4^3}{6} + \dfrac{x_6^2}{6} + \dfrac{x_{12}}{3}\).

Como hemos elegido colorantes usando blanco y negro, tendría sentido sustituir a all\(i\) in\(P_{C_{12}}\) now\(x_i=b^i+w^i\) para encontrar el número de escalas\(k\) de notas. Sin embargo, hay un atajo conveniente que podemos tomar para que la función generadora resultante se parezca más a aquellas a las que nos acostumbramos en el Capítulo 8. La información sobre cuántas notas no están incluidas en nuestra escala (el número de color blanco) se puede deducir del número que se incluyen. Así, podemos eliminar el uso de la variable\(w\), reemplazándola por 1. Ahora encontramos

\(P_{C_{12}}(1+b,1+b^2,…,1+b^{12})=b^{12}+b^{11}+6b^{10}+19b^9+43b^8+66b^7+80b^6+66b^5+43b^4+19b^3+6b^2+b+1\).

A partir de esto, podemos deducir que el número de escalas con\(k\) notas es el coeficiente encendido\(b^k\). Por lo tanto, la respuesta a nuestra pregunta al inicio del capítulo sobre el número de escalas de 6 notas es 80.

15.5.2 Enumeración de isómeros

El benceno es un compuesto químico con fórmula\(C_6H_6\), lo que significa que consta de seis átomos de carbono y seis átomos de hidrógeno. Estos átomos están unidos de tal manera que los seis átomos de carbono forman un anillo hexagonal con enlaces simples y dobles alternantes. Un átomo de hidrógeno está unido a cada átomo de carbono (en el exterior del anillo). A partir del benceno es posible formar otros compuestos químicos que forman parte de una familia conocida como hidrocarburos aromáticos. Estos compuestos se forman reemplazando uno o más de los átomos de hidrógeno por átomos de otros elementos o grupos funcionales como\(CH_3\) (grupo metilo) o\(OH\) (grupo hidroxilo). Debido a que hay seis opciones para las cuales los átomos de hidrógeno reemplazar, se pueden formar moléculas con la misma fórmula química pero diferentes estructuras de esta manera. Tales moléculas se llaman isómeros. En esta subsección, veremos cómo se puede utilizar el Teorema de Enumeración de Pólya para determinar el número de isómeros del hidrocarburo aromático xilenol (también conocido como dimetilfenol).

Antes de entrar en la estructura molecular del xilenol, necesitamos discutir el grupo de permutación que actuará sobre un anillo de benceno. Al igual que con nuestro ejemplo de colorear los vértices del cuadrado, encontramos que aquí hay rotaciones y volteretas en juego. De hecho, el grupo que requerimos es el grupo diedro del hexágono,\(D_{12}\). Si numeramos los seis átomos de carbono en el orden de las agujas del reloj como 1,2,... ,6, entonces encontramos que la rotación en sentido horario por\(60^\circ\) corresponde a la permutación\(r=(123456)\). Las otras rotaciones son las potencias superiores de\(r\), como se muestra en la Figura 15.13. El volteo a través del eje vertical es la permutación\(f=(16)(25)(34)\). Los elementos restantes de\(D_{12}\) (que no sean la identidad\(ι\)) se pueden realizar todos como una rotación seguida de este giro. La lista completa de permutaciones se muestra en la Figura 15.13, donde cada permutación va acompañada del monomio que aporta al índice de ciclo.

Figura 15.13. Representación de ciclo de permutaciones en\(D_{12}\)

Con los monomios asociados a las permutaciones en\(D_{12}\) identificados, podemos anotar el índice de ciclo

\(P_{D_{12}}(x_1,…,x_6)=\dfrac{1}{12}(x_1^6+2x_6^1+2x_3^2+4x_2^3+3x_1^2x_2^2)\).

Con el índice de ciclo determinado, ahora volvemos nuestra atención a usarlo para encontrar el número de isómeros del xilenol. Este hidrocarburo aromático tiene tres moléculas de hidrógeno, dos grupos metilo y un grupo hidroxilo unido a los átomos de carbono. Recordando que los átomos de hidrógeno son los predeterminados del benceno, podemos ignorarlos más o menos a la hora de elegir la sustitución adecuada para el\(x_i\) en el índice de ciclo. Si dejamos\(m\) denotar grupos metilo y grupos\(h\) hidroxilo, entonces podemos\(x_i=1+m^i+h^i\) sustituirlos\(P_{D_{12}}\). Esta sustitución da la función generadora

\(1+h+3h^2+3h^3+3h^4+h^5+h^6+m+3hm+6h^2m+6h^3m+3h^4m+h^5m+3m^2+6hm^2+11h^2m^2+6h^3m^2+3h^4m^2+3m^3+6hm^3+6h^2m^3+3h^3m^3+3m^4+3hm^4+3h^2m^4+m^5+hm^5+m^6\).

Dado que el xilenol tiene un grupo hidroxilo y dos grupos metilo, estamos buscando el coeficiente\(hm^2\) en esta función generadora. El coeficiente es 6, por lo que hay seis isómeros de xilenol.

En su trabajo original, Pólya utilizó sus técnicas para enumerar el número de isómeros de los alcanos\(C_nH_{2n+2}\). Cuando se modelan como gráficas, estos compuestos químicos son tipos especiales de árboles. Desde entonces, el Teorema de Enumeración de Pólya se ha utilizado para enumerar isómeros para muchos compuestos químicos diferentes.

15.5.3 Recuento de gráficas no isomórficas

Contar las gráficas con conjunto de vértices no\([n]\) es difícil. Existen\(C(n,2)\) posibles bordes, cada uno de los cuales puede ser incluido o excluido. Así, hay gráficas\(2^{C(n,2)}\) etiquetadas en\(n\) vértices. Es solo un poco de pensamiento extra determinar que si solo quieres contar las gráficas etiquetadas en\(n\) vértices con\(k\) bordes, simplemente debes elegir un subconjunto\(k\) -element del conjunto de todos los bordes\(C(n,2)\) posibles. Por lo tanto, hay

\(\dbinom{\binom{n}{2}}{k}\)

gráficas con conjunto de vértices\([n]\) y exactamente\(k\) bordes.

Un problema más difícil surge cuando queremos comenzar a contar gráficas no isomórficas en\(n\) vértices. (También se puede pensar en estos como gráficos sin etiquetar). Por ejemplo, en la Figura 15.14, mostramos cuatro gráficas etiquetadas diferentes en cuatro vértices. Las tres primeras gráficas que se muestran allí, sin embargo, son isomórficas entre sí. Así, en la figura sólo se ilustran dos gráficas no isomórficas sobre cuatro vértices. Para dar cuenta de los isomorfismos, necesitamos poner en juego el Teorema de Enumeración de Pólya.

Figura 15.14. Cuatro gráficas etiquetadas en cuatro vértices

Comenzamos considerando todas las\(2^{C(n,2)}\) gráficas con conjunto de vértices\([n]\) y eligiendo un grupo de permutación adecuado para actuar en la situación. Dado que cualquier vértice puede mapearse a cualquier otro vértice, el grupo simétrico\(S_4\) actúa sobre los vértices. Sin embargo, tenemos que tener cuidado con cómo encontramos el índice de ciclo aquí. Cuando estábamos trabajando con coloraciones de los vértices del cuadrado, nos dimos cuenta de que todos los vértices que aparecen en el mismo ciclo de una permutación\(\pi\) tenían que ser coloreados del mismo color. Como nos preocupan los bordes aquí y no los colores de vértices, lo que realmente necesitamos para una permutación para fijar un gráfico es que cada borde se envíe a un borde y cada no borde se envíe a un no borde. Para ser específicos, si {1,2} es un borde de algunos\(\textbf{G}\) y se\(\pi∈S_4\) fija\(\textbf{G}\), entonces también\(\{ \pi (1), \pi (2)\}\) debe ser un borde de\(\textbf{G}\). Del mismo modo, si los vértices 3 y 4 no son adyacentes en\(\textbf{G}\), entonces\(\pi(3)\) y también\(\pi(4)\) deben ser no adyacentes en\(\textbf{G}\).

Para dar cuenta de aristas, pasamos del grupo simétrico\(S_4\) a su grupo de pares\(S_4^{(2)}\). Los objetos que\(S_4^{(2)}\) permutan son los subconjuntos de 2 elementos de {1,2,3,4}. Para facilitar la notación, denotaremos el subconjunto de 2 elementos\(\{i,j\}\) por\(e_{ij}\). Para encontrar las permutaciones en\(S_4^{(2)}\), consideramos las permutaciones de vértice en\(S_4\) y vemos cómo permutan el\(e_{ij}\). La permutación\(ι=(1)(2)(3)(4)\) de identidad de\(S_4\) corresponde a la permutación\(ι=(e_{12})(e_{13})(e_{14})(e_{23})(e_{24})(e_{34})\) de identidad de\(S_4^{(2)}\). Ahora consideremos la permutación (12) (3) (4). Se corrige\(e_{12}\) ya que envía 1 a 2 y 2 a 1. También se fija\(e_{34}\) fijando 3 y 4. Sin embargo, se intercambia\(e_{13}\) con\(e_{23}\) (3 es fijo y 1 se intercambia con 2) y\(e_{14}\) con\(e_{24}\) (1 se envía a 2 y 4 es fijo). Así, la permutación correspondiente de pares es\((e_{12})(e_{13}e_{23})(e_{14}e_{24})(e_{34})\). Para otro ejemplo, considere la permutación (123) (4). Corresponde a la permutación\((e_{12}e_{23}e_{13})(e_{14}e_{24}e_{34})\) en\(S_4^{(2)}\).

Como sólo estamos tras el índice de ciclo de\(S_4^{(2)}\), no necesitamos encontrar todas las 24 permutaciones en el grupo de pares. Sin embargo, sí necesitamos conocer los tipos de esas permutaciones en términos de longitudes de ciclo para poder asociar los monomios apropiados. Para los tres ejemplos que hemos considerado, la estructura de ciclo de la permutación en el grupo de pares no depende de la permutación original en\(S_4\) otra que no sea para su estructura de ciclo. Cualquier permutación\(S_4\) consistente en un ciclo 2 y dos 1-ciclos corresponderá a una permutación con dos 2-ciclos y dos 1-ciclos en\(S_4^{(2)}\). Una permutación\(S_4\) con un ciclo de 3 y uno de 1 ciclo corresponderá a una permutación con dos ciclos de 3 en el grupo de pares. Al considerar un ejemplo de una permutación\(S_4\) consistente en un solo ciclo de 4 ciclos, encontramos que la permutación correspondiente en el grupo de pares tiene un ciclo de 4 y uno de 2 ciclos. Finalmente, una permutación\(S_4\) consistente en dos 2-ciclos corresponde a una permutación en\(S_4^{(2)}\) tener dos 2-ciclos y dos 1-ciclos. (El ejercicio 15.6.8 le pide verificar estas afirmaciones usando permutaciones específicas).

Ahora que conocemos la estructura del ciclo de las permutaciones en\(S_4^{(2)}\), la única tarea que queda antes de que podamos encontrar su índice de ciclo de es determinar cuántas permutaciones tienen cada una de las posibles estructuras de ciclo. Para ello, volvemos a referirnos a las permutaciones del grupo simétrico\(S_4\). Una permutación que consiste en un solo ciclo de 4 comienza con 1 y luego tiene 2, 3 y 4 en cualquiera de los 3! =6 órdenes posibles, por lo que hay 6 tales permutaciones. Para las permutaciones que consisten en un ciclo 1 y un ciclo 3, hay 4 formas de elegir el elemento para el ciclo 1 y luego 2 formas de organizar los otros tres como un ciclo de 3. (Recuerde que el más pequeño de ellos debe colocarse primero, por lo que luego hay 2 formas de organizar los dos restantes). Así, hay 8 de tales permutaciones. Para una permutación que consta de dos ciclos de 1 y uno de 2 ciclos, hay\(C(4,2)=6\) formas de elegir los dos elementos para el ciclo 2. Así, hay 6 de tales permutaciones. Para que una permutación consista en dos 2 ciclos, hay\(C(4,2)=6\) formas de elegir dos elementos para el primer ciclo de 2. Los otros dos se ponen luego en el segundo ciclo de 2. Sin embargo, esto cuenta cada permutación dos veces, una para cuando el primer ciclo es el par elegido y una vez para cuando es el “otros dos”. Así, hay 3 permutaciones que constan de dos ciclos de 2. Finalmente, solo\(ι\) consta de cuatro 1-ciclos.

Ahora estamos preparados para anotar el índice de ciclo del grupo de pares

\(P_{S_4^{(2)}}(x_1,…,x_6)=\dfrac{1}{24}(x_6^1+9x_1^2x_2^2+8x_3^2+6x_2x_4)\).

Para usar esto para enumerar gráficas, ahora podemos hacer la sustitución\(x_i=1+x^i\) por\(1≤i≤6\). Esto nos permite dar cuenta de las dos opciones de que una arista no esté presente o esté presente. Al hacerlo, encontramos

\(P_{S_4^{(2)}}(1+x,…,1+x^6)=1+x+2x^2+3x^3+2x^4+x^5+x^6\)

es la función generadora para el número de gráficos de 4 vértices con\(m\) bordes,\(0≤m≤6\). Para encontrar el número total de gráficas no isomórficas en cuatro vértices, sustituimos\(x=1\) en este polinomio. Esto nos permite concluir que hay 11 gráficas no isomórficas en cuatro vértices, una marcada reducción de las 64 gráficas etiquetadas.

Se pueden utilizar las técnicas de esta subsección, dada la suficiente potencia de cálculo, para encontrar el número de gráficas no isomórficas en cualquier número de vértices. Para 30 vértices, hay

\(334494316309257669249439569928080028956631479935393064329967834887217734534880582749030521599504384 \approx 3.3×10^{98}\)

gráficas no isomórficas, en comparación con gráficas\(2^{435} \approx 8.9×10^{130}\) etiquetadas en 30 vértices. El número de gráficas no isomórficas con precisión de 200 bordes es

\(3133824809970726276258772475733640185446767033655017855836082677050799699893512219821910360979601 \approx 3.1×10^{96}\).

La última parte de la pregunta sobre la enumeración gráfica al inicio del capítulo se refería a enumerar las gráficas en algún número de vértices en los que cada vértice tiene grado\(r\). Si bien esto puede parecer que podría abordarse usando las técnicas de este capítulo, resulta que no puede debido a la mayor dependencia entre donde se mapean los vértices.