6.4: Conteo Pólya-Redfield
- Page ID
- 117073
Supongamos que nos interesa un inventario más detallado de los colorantes de un objeto, es decir, en lugar del número total de colorantes buscamos el número de colorantes con un número dado de cada color.
Ejemplo\(\PageIndex{1}\)
¿Cuántas formas distintas hay de colorear los vértices de un módulo pentágono regular\(D_5\) para que un vértice sea rojo, dos sean azules y dos sean verdes?
Podemos acercarnos a esto como antes, es decir, la respuesta es
\[{1\over|D_5|}\sum_{\sigma\in D_5}|\text{fix}(\sigma)|,\nonumber\]
donde\(\text{fix}(\sigma)\) ahora significa los colorantes con uno rojo, dos azules y dos verdes que se fijan por\(\sigma\). Ya no podemos usar la simple expresión de Corolario 6.3.2.
La permutación de identidad fija todos los colorantes, así que necesitamos saber cuántos colorantes del pentágono usan uno rojo, dos azules y dos verdes. Este es un problema fácil de contar: el número es\({5\choose2}{3\choose2}=30\).
Si\(\sigma\) es una rotación no trivial,\(|\text{fix}(\sigma)|=0\), ya que los únicos colorantes fijados por una rotación tienen todos los vértices del mismo color.
Si\(\sigma\) es un reflejo, el vértice único fijado por\(\sigma\) debe ser rojo, y luego los 2 ciclos restantes son de color azul y verde en una de dos formas, entonces\(|\text{fix}(\sigma)|=2\).
Por lo tanto, el número de colorantes distintos es\[{1\over10}(30+0+0+0+0+2+2+2+2+2)=4.\nonumber\]
Lo que buscamos es una manera de agilizar este proceso, ya que en general los cómputos de\(|\text{fix}(\sigma)|\) pueden ser tediosos. Comenzamos por refundir la fórmula del Corolario 6.3.2.
Definición\(\PageIndex{1}\): Type of a Permutation
El tipo de una permutación\(\sigma\in S_n\) es\(\tau(\sigma)=(\tau_1(\sigma),\tau_2(\sigma),\ldots,\tau_n(\sigma))\), donde\(\tau_i(\sigma)\) está el número de\(i\) -ciclos en la forma de ciclo de\(\sigma\).
Tenga en cuenta que\(\sum_{i=1}^n \tau_i(\sigma)=\#\sigma\). Ahora en lugar de lo simple
\[{1\over|G|}\sum_{\sigma\in G} k^{\#\sigma}\nonumber\]
escribamos
\[{1\over|G|}\sum_{\sigma\in G} x_1^{\tau_1(\sigma)}x_2^{\tau_2(\sigma)} \cdots x_n^{\tau_n(\sigma)}.\nonumber\]
Si sustituimos\(x_i=k\) por cada\(i\), obtenemos la forma original de la suma, pero la nueva versión lleva más información sobre cada una\(\sigma\).
Supongamos que queremos saber el número de colorantes fijados por algunos\(\sigma\) que usan\(i\) rojos y\(j\) azules, donde por supuesto\(i+j=n\). Usando ideas familiares a partir de la generación de funciones, considere la siguiente expresión:
\[(r+b)^{\tau_1(\sigma)}(r^2+b^2)^{\tau_2(\sigma)} \cdots (r^n+b^n)^{\tau_n(\sigma)}.\nonumber\]
Si multiplicamos, obtenemos una suma de términos de la forma\(r^pb^q\), cada uno representando alguna forma particular de colorear los vértices de los ciclos rojo y azul de manera que el número total de vértices rojos es\(p\) y el número de vértices azules es\(q\), y además esta coloración será fijada por\(\sigma\). Cuando recolectamos términos similares, el coeficiente de\(r^ib^j\) es el número de colorantes fijados por\(\sigma\) ese uso\(i\) rojos y\(j\) azules. Esto significa que el coeficiente de\(r^ib^j\) in
\[\sum_{\sigma\in G} (r+b)^{\tau_1(\sigma)}(r^2+b^2)^{\tau_2(\sigma)} \cdots (r^n+b^n)^{\tau_n(\sigma)}\nonumber\]
es
\[\sum_{\sigma\in G} |\text{fix}(\sigma)|\nonumber\]
donde\(\text{fix}(\sigma)\) está el conjunto de colorantes usando\(i\) rojos y\(j\) azules que se fijan por\(\sigma\). Finalmente, entonces, el número de colorantes distintos usando\(i\) rojos y\(j\) azules es este coeficiente dividido por\(|G|\). Esto quiere decir que multiplicando
\[{1\over |G|}\sum_{\sigma\in G}(r+b)^{\tau_1(\sigma)}(r^2+b^2)^{\tau_2(\sigma)} \cdots (r^n+b^n)^{\tau_n(\sigma)}\nonumber\]
y recopilando términos similares, obtenemos una lista del número de colorantes distintos usando cualquier combinación de rojos y azules, cada uno el coeficiente de un término diferente; llamamos a esto el inventario de colorantes. Si sustituimos\(r=1\) y\(b=1\), obtenemos la suma de los coeficientes, es decir, el número total de coloraciones distintas con dos colores.
Definición\(\PageIndex{2}\): Cycle Index
El índice de ciclo de\(G\) es\[P_G={1\over |G|}\sum_{\sigma\in G}\prod_{i=1}^n x_i^{\tau_i(\sigma)}.\nonumber\]
Ejemplo\(\PageIndex{2}\)
Consideremos de nuevo el Ejemplo 6.3.1, en el que encontramos el número de colorantes de un cuadrado con dos colores. El índice de ciclo de\(D_4\) es\[{1\over8}( x_1^4+x_4^1+x_2^2+x_4^1+x_2^2+x_2^2+x_1^2x_2+x_1^2x_2 ) ={1\over8}x_1^4 + {1\over4}x_1^2x_2 + {3\over8}x_2^2 + {1\over4}x_4.\nonumber\] Sustituyendo como arriba da\[{1\over8}(r+b)^4 + {1\over4}(r+b)^2(r^2+b^2) + {3\over8}(r^2+b^2)^2 + {1\over4}(r^4+b^4) =r^4 + r^3b + 2r^2b^2 + rb^3 + b^4.\nonumber\] Así hay uno todo de color rojo, uno con tres rojos y uno azul, y así sucesivamente, como se muestra en la Figura 6.3.4.
No hay nada especial en el uso de dos colores. Si queremos usar tres colores,\(r^i+b^i+g^i\) sustituimos\(x_i\) en el índice de ciclo, y por\(k\) colores sustituimos algo así como\(c_1^i+c_2^i+c_3^i+\cdots+c_k^i\).
Ejemplo \(\PageIndex{3}\)
Hagamos el número de 3 colores del cuadrado. Como ya tenemos el índice de ciclo, solo necesitamos sustituirlo\(x_i=r^i+b^i+g^i\) y expandirnos. Obtenemos\[\eqalign{ {1\over8}(r+b+g)^4 &+ {1\over4}(r+b+g)^2(r^2+b^2+g^2) + {3\over8}(r^2+b^2+g^2)^2 + {1\over4}(r^4+b^4+g^4)\cr ={}&b^4 + b^3g + b^3r + 2b^2g^2 + 2b^2gr + 2b^2r^2 + bg^3 + 2bg^2r + 2bgr^2 +\cr &br^3 + g^4 + g^3r + 2g^2r^2 + gr^3 + r^4.\cr }\nonumber\] Entonces, por ejemplo, hay dos cuadrados con dos vértices azules, uno verde, y otro rojo, del\(b^2gr\) término.
Ejemplo \(\PageIndex{4}\)
Consideremos de nuevo el Ejemplo 6.3.2, en el que contamos el número de gráficas de cuatro vértices. Siguiendo ese ejemplo, obtenemos\[P_G={1\over 24}(x_1^6+6x_2x_4+8x_3^2+3x_1^2x_2^2+6x_1^2x_2^2),\nonumber\] y sustituyendo por las variables\(x_i\) da
\[r^6 + r^5b + 2r^4b^2 + 3r^3b^3 + 2r^2b^4 + rb^5 + b^6.\nonumber\]
Recordemos que los “colores” de los bordes en este ejemplo son “incluidos” y “excluidos”. Si configuramos\(b=1\) y\(r=i\) (para “incluido”) obtenemos
\[i^6 + i^5 + 2i^4 + 3i^3 + 2i^2 + i + 1,\nonumber\]
interpretado como una gráfica con 6 aristas, una con 5, dos con 4, tres con 3, dos con 2, una con 1, y una con cero aristas, ya que\(1=i^0\).
Es posible, aunque un poco difícil, ver que para\(n\) los vértices el índice de ciclo es
\[ P_G=\sum_{\bf j}\prod_{k=1}^n{1\over k^{j_k} j_k!} \prod_{k=1}^{\lfloor n/2\rfloor}(x_{k} x_{2k}^{k-1})^{j_{2k}} \!\!\prod_{k=1}^{\lfloor (n-1)/2\rfloor}\!\!x_{2k+1}^{kj_{2k+1}} \prod_{k=1}^{\lfloor n/2\rfloor} x_k^{kC(j_k,2)} \!\!\!\!\prod_{1\le r< s\le n-1}\!\!\!\!\!\!\!\! x_{\text{lcm}(r,s)}^{\gcd(r,s)j_rj_s},\nonumber \]
donde las sumas están sobre todas las particiones\({\bf j}=(j_1,j_2,\ldots,j_n)\) de\(n\), es decir, sobre todas\(\bf j\) tales que\(j_1+2j_2+3j_3+\cdots+nj_n=n\), y\(C(m,2)={m\choose2}\). De ahí viene la Fórmula 6.3.1, sustituyendo\(x_i=2\) a todos\(i\).
Con esta fórmula y una computadora es fácil calcular el inventario de gráficos\(n\) -vértices cuando no\(n\) es demasiado grande. Cuando\(n=5\), el inventario es
\[ i^{10} + i^9 + 2i^8 + 4i^7 + 6i^6 + 6i^5 + 6i^4 + 4i^3 + 2i^2 + i+1.\nonumber \]
Podemos usar Sage para hacer los cálculos involucrados en la búsqueda del índice de ciclo para las gráficas.
Definimos dos funciones útiles; la función “polya” produce el índice de ciclo para las gráficas en\(n\) vértices.
def nextpar(mults, n):
if mults == []:
return Partitions(n).first().to_exp(n)
p = Partition(exp=mults).next()
if p != False:
return(p.to_exp(n))
else:
return p
def polya(n):
var("x");
global y;
y = list(var('x_%d' % i) for i in range(binomial(n,2)+1));
max_sub = n;
j = Partition([0]);
j = nextpar(j,n);
p=0;
lim1 = floor(n / 2); lim2 = floor((n-1) / 2);
while j != False:
t = 1;
for k in range(1,lim1+1):
if j[2*k-1] > 0:
t = t * y[k]^j[2*k-1];
if (j[2*k-1] > 0) and (k > 1):
t = t * y[2*k]^((k-1)*j[2*k-1]);
if j[k-1] >= 2:
t = t * y[k]^(k*binomial(j[k-1],2));
for k in range(1,lim2+1):
if j[2*k+1-1] > 0:
t = t * y[2*k+1]^(k*j[2*k+1-1]);
for r in range(1,n-1):
for s in range(r+1,n):
if (j[r-1]>0) and (j[s-1]>0):
t = t* y[lcm(r,s)]^(gcd(r,s)*j[r-1]*j[s-1]);
max_sub = max(max_sub,lcm(r,s))
for k in range(1,n+1):
if (k > 1) and (j[k-1] > 0):
t = t / (k^j[k-1]);
if j[k-1] > 1:
t = t / (factorial(j[k-1]));
p = p + t;
j = nextpar(j,n);
return(p);
Ahora podemos calcular el índice de ciclo para\(n=4\) como en el ejemplo anterior.
f=polya(4) show(expand(f))
Entonces podemos obtener el inventario:
i=var('i')
s=dict()
for j in range(1,7):
s[y[j]]=(i^j+1)
show(expand(f.subs(s)))
Y obtenemos el número total de gráficas sustituyendo 1 por\(i\) en el inventario.
show(f.subs(s).subs(i=1))