Enumeración de Polya: Generar configuraciones a partir del índice de ciclos

Question

Tengo una cuadrícula de 3x3.

$$\begin{array}{|c|c|c|} \hline 1 & 2 & 3\\ \hline 4 & 5 & 6\\ \hline 7 & 8 & 9\\ \hline \end{array}$$

Las simetrías son las 4 rotaciones (0, 90, 180, 270), y las 4 reflexiones (arriba/abajo, izquierda/derecha, 2 diagonales). Grupo diédrico 4, creo.

El índice del ciclo se convierte en:

$$ \frac{1}{8}[x^9_1 + 2x^1_1x^2_4 + x^1_1x^4_2+4x^3_1x^3_2] $$

Quiero colorear la cuadrícula de dos colores, así que amplío con el Teorema de Enumeración de Polya: $$ \frac{1}{8}[(a+b)^9 + 2(a+b)(a^4+b^4)^2 + (a+b)(a^2+b^2)^4+4(a+b)^3(a^2+b^2)^3] $$ Ampliando sólo el primer término $(a+b)^9 $ tiene términos $$ a^9 + 9 a^8 b + 36 a^7 b^2 + 84 a^6 b^3 + 126 a^5 b^4 + 126 a^4 b^5 + 84 a^3 b^6 + 36 a^2 b^7 + 9 a b^8 + b^9 $$

En esta forma ampliada, el $126a^5b^4$ significa que tengo alrededor de 126 configuraciones con 5 de color $a$ y 4 de color $b$ (probablemente menos, ya que no he dividido).

¿Hay alguna manera de enumerar estas 126 configuraciones únicas, aparte de la fuerza bruta?

Me gustaría ampliarlo a algo así como una cuadrícula de 6x6, pero estos coeficientes no harán más que aumentar.

Answer 1

La enumeración de Pólya es buena para contar (encontrar el número de), pero no para enumerar.

Pero sí, hay métodos eficientes para enumerar también las configuraciones sujetas a la acción del grupo, aparte de la fuerza bruta. Véase esta pregunta del modus operandi para sugerencias como generación ordenada . (En uno de los comentarios, Richard Stanley cita a Gill Williamson: "La teoría de la enumeración de Pólya no suele ser una buena herramienta para enumerar realmente el sistema de representantes...").

En cuanto a su problema actual: SageMath y su IntegerVectorsModPermutationGroup puede hacerlo, y es posible que quieras estudiar cómo lo hace (es decir, estudiar el algoritmo). En cualquier caso, tener una solución computacional te da algo para comprobar tus soluciones manuales (ya sea los recuentos o los listados).

Representar el color $a$ como $0$ y $b$ como $1$ Aquí están las configuraciones con una sola $b$ :

sage: G=PermutationGroup([[(1,3,9,7),(2,6,8,4)],[(1,3),(7,9),(4,6)]])
sage: len(G)
8
sage: G.is_isomorphic(DihedralGroup(4))
True
sage: IV1=IntegerVectorsModPermutationGroup(G, sum=1, max_part=1)
sage: list(IV1)
[[1, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 1, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0, 0, 0, 0]]

Puede que quieras comprobar (1) si esto tiene sentido [pista: creo que sí; piensa en las posibilidades en las que ese $b$ podría ir en la parrilla], (2) si el recuento de su enumeración de Pólya coincide con esto (da $3$ ).

Por cuatro $b$ obtenemos $23$ configuraciones.

sage: IV4=IntegerVectorsModPermutationGroup(G, sum=4, max_part=1)
sage: list(IV4)
[[1, 1, 1, 1, 0, 0, 0, 0, 0],
 [1, 1, 1, 0, 1, 0, 0, 0, 0],
 [1, 1, 1, 0, 0, 0, 1, 0, 0],
 [1, 1, 1, 0, 0, 0, 0, 1, 0],
 [1, 1, 0, 1, 1, 0, 0, 0, 0],
 [1, 1, 0, 1, 0, 1, 0, 0, 0],
 [1, 1, 0, 1, 0, 0, 0, 0, 1],
 [1, 1, 0, 0, 1, 1, 0, 0, 0],
 [1, 1, 0, 0, 1, 0, 1, 0, 0],
 [1, 1, 0, 0, 1, 0, 0, 1, 0],
 [1, 1, 0, 0, 1, 0, 0, 0, 1],
 [1, 1, 0, 0, 0, 1, 1, 0, 0],
 [1, 1, 0, 0, 0, 1, 0, 1, 0],
 [1, 1, 0, 0, 0, 1, 0, 0, 1],
 [1, 1, 0, 0, 0, 0, 1, 1, 0],
 [1, 1, 0, 0, 0, 0, 1, 0, 1],
 [1, 1, 0, 0, 0, 0, 0, 1, 1],
 [1, 0, 1, 0, 1, 0, 1, 0, 0],
 [1, 0, 1, 0, 1, 0, 0, 1, 0],
 [1, 0, 1, 0, 0, 0, 1, 0, 1],
 [1, 0, 0, 0, 1, 1, 0, 1, 0],
 [0, 1, 0, 1, 1, 1, 0, 0, 0],
 [0, 1, 0, 1, 0, 1, 0, 1, 0]]
sage: len(_)
23