$3$ - colorantes de una tabla$3×3$ con uno de$3$ colores hasta simetrías

Question

El Color de cada celda de una $3×3$ mesa con uno de $3$ colores. ¿Cuál es el número de maneras de hacerlo si las células adyacentes tienen diferentes colores?

---

Por supuesto, tenemos en cuenta dos obras de la misma (o equivalente) si existen reflexión o rotación que tomar de uno a otro. Así

$$ \begin{array} {|r|r|r|} \hline \color{blue}{B}& \color{yellow}{Y} &\color{red}{R} \\ \hline \color{red}{R}& \color{red}{R}&\color{red}{R}\\ \hline \color{red}{R}& \color{red}{R}& \color{red}{R} \\ \hline \end{array} \;\;\;\;\;{\rm y} \;\;\;\;\; \begin{array} {|r|r|r|} \hline \color{red}{R}& \color{red}{R}& \color{blue}{B} \\ \hline \color{red}{R}& \color{red}{R}& \color{yellow}{Y} \\ \hline \color{red}{R}& \color{red}{R}& \color{red}{R} \\ \hline \end{array} $$ son los mismos colores.

Desde células marcadas son "independientes" podemos colores al azar, pero no con todos los 3 colores.

\begin{array} {|r|r|r|} \hline & X & \\ \hline X & &X \\ \hline & X& \\ \hline \end{array}

Caso 1: Si todos los $X$ son de color con el mismo color, a continuación, para cada una de marcar la celda tenemos 2 posibilites. Así que en este caso se ha $3\cdot 2^{5}$ posible de colores. Pero es evidente que algunas de ellas son equivalentes. ¿Qué debo hacer? Divida esta con 4? O 16? Algo más?

Caso 2: $Y$ es de diferente color, a continuación, $X$. Ahora tenemos $3$ colores para $Y$ e $2$ para $X$. Resto de los lugares que pueden dar color a $1^3\cdot 2^2$ así tenemos $6\cdot 2^{2}$ posible de colores. Pero de nuevo las reflexiones a través de mediados colum nos dan equivalente colorantes por lo tanto debemos dividir esta por $2$? \begin{array} {|r|r|r|} \hline & Y & \\ \hline X & &X \\ \hline & X& \\ \hline \end{array}

Caso 3:... \begin{array} {|r|r|r|} \hline & Y & \\ \hline Y & &X \\ \hline & X& \\ \hline \end{array}

Es más elegante abordaje?

Answer 1

Podemos utilizar Burnside del lema a cuenta de simetrías. Por la OEIS, hay 246 3 coloraciones de un etiquetado de 3×3 de la cuadrícula gráfico (es decir, antes de la contabilidad de simetría).

Este gráfico de la no-identidad simetrías son como sigue. La forma general de una coloración invariantes bajo esta simetría se muestra, a continuación, un cálculo del número de coloraciones.

• 90° a la izquierda/derecha rotaciones. Una coloración invariantes bajo esta transformación se parece a esto: $$\begin{array}{|r|r|r|} \hline a&b&a\\ \hline b&c&b\\ \hline a&b&a\\\hline\end{array}$$ Después de $b$ es elegido, tenemos dos posibilidades para cada $a,c$. Por lo tanto, hay $3×2×2=12$ tales colorantes invariante bajo cada una de estas simetrías.
• Rotación de 180°. $$\begin{array}{|r|r|r|} \hline a&b&c\\ \hline d&e&d\\ \hline c&b&a\\\hline\end{array}$$ Cualquiera de las $b,d$ son de diferentes colores (6 modos), en cuyo caso $a,c,e$ sólo puede suponer el tercer color, o $b,d$ son de la misma (3 vías) y $a,c,e$ puede ser uno de los dos colores. Hay $6×1^3+3×2^3=30$ invariante coloraciones.
• Horizontal/vertical reflexiones. $$\begin{array}{|r|r|r|} \hline a&b&c\\ \hline d&e&f\\ \hline a&b&c\\\hline\end{array}$$ Esto es equivalente a la cifra de 3-coloraciones de un 2×3 cuadrícula gráfico. Apelando a la OEIS de nuevo, vemos que hay 54 tales colorantes para cada simetría.
• Diagonal reflexiones. $$\begin{array}{|r|r|r|} \hline a&b&c\\ \hline d&e&b\\ \hline f&d&a\\\hline\end{array}$$ Esto es equivalente al número de coloraciones de un cuadrado, de 18 años de acuerdo a la OEIS, multiplicado por 4, con un rendimiento del 72. La plaza está formada por $a,b,d,e$, y para cada uno de coloración de la plaza de la $c,f$ puede ser cualquiera de los dos colores no se utiliza para $b,d$ respectivamente, por lo tanto el $2^2$ multiplicador.

Burnside del lexema, a continuación, da el número de coloraciones hasta simetrías como $$\frac{246+2×12+30+2×54+2×72}8=\color{red}{69}$$

Answer 2

Me permito publicar un puntero. El siguiente MSE enlace a partir de las once hace meses características orbitales cromática polinomios, que contar adecuado para el color de un gráfico de las simetrías de su automorfismos. Existe una amplia documentación en ese enlace. El código que se ha publicado no es fácil de aplicar aquí: subyacente gráfico con los bordes de adyacencia esta el tres por tres de cuadrícula gráfico. Nos codificar de la siguiente manera:

SQUARE3BY3 :=
proc()
opción de recordar;

volver
[9,
 {{1, 2}, {2, 3},
 {4, 5}, {5, 6},
 {7, 8}, {8, 9},
 {1, 4}, {2, 5}, {3, 6},
 {4, 7}, {5, 8}, {6, 9}},

 [[1,2,3,4,5,6,7,8,9], # identidad
 [3,6,9,2,5,8,1,4,7], # 90 grados
 [7,4,1,8,5,2,9,6,3], # -90 grados
 [9,8,7,6,5,4,3,2,1], # 180 grados

 [7,8,9,4,5,6,1,2,3], # flip horizontal
 [3,2,1,6,5,4,9,8,7], # vertical flip

 [1,4,7,2,5,8,3,6,9], # cayendo en diagonal
 [9,6,3,8,5,2,7,4,1]]]; # el aumento de diagonal

end;

El comando de Maple OCP(SQUARE3BY3()); inmediatamente después, los rendimientos de la OCP:

$$P(k) = 1/8\,{k}^{9}+8\,k-{\frac {133\,{k}^{2}}{4}}-3/2\,{k}^{8} +{\frac {33\,{k}^{7}}{4}}-{\frac {53\,{k}^{6}}{2}} +{\frac {217\,{k}^{5}}{4}}-{\frac {291\,{k}^{4}}{4}} +{\frac {507\,{k}^{3}}{8}}.$$

Este rendimientos de hasta doce colores de la secuencia

$$0, 2, 69, 1572, 19865, 153480, 830802, 3476144, 12003462, \\35757630, 94780235, 228579252, \ldots$$

lo que confirma el valor de tres colores que fue el primero en aparecer.

Nota, ya que por los comentarios. El valor de $P(k)$ de este OCP cuenta el número de colorantes utilizando en la mayoría de las $k$ colores. Podemos calcular $P'(k)$ que da el buen colorantes utilizando exactamente $k$ colores inclusión-exclusión. Aquí los nodos de la poset son subconjuntos $Q$de $[k]$ representación adecuada de los colorantes usando un subconjunto de los colores en $Q$, la cual es contada por $P(|Q|).$ para colorear utilizando exactamente los colores de algún juego $R$ está representado por todos los nodos correspondientes a superseries $Q$ de $R.$ Con el peso de ser $(-1)^{k-|Q|}$los los colorantes utilizando exactamente $k$ colores sólo se producen en $Q=[k]$ con peso $(-1)^{k-|Q|} = (-1)^{0} = 1.$ Para colorear utilizando exactamente $R\subset [k]$ colores está representado por todos los $Q$ tales que $R \subseteq Q \subseteq [k]$, con un peso total de

$$\sum_{I'\subseteq [k] \setminus R} (-1)^{k-|R\cup R'|} = (-1)^{k-|R|} \sum_{i=0}^{|[k]\setminus R|} {|[k]\setminus R| \elegir r} (-1)^{-r} = 0.$$

Por lo tanto sólo los colorantes con exactamente $k$ colores contribuir y nos encontrar

$$P'(k) = \sum_{Q\subseteq [k]} (-1)^{k-|Q|} P(|P|) = \sum_{q=0}^k {k\elegir q} (-1)^{k-q} P(q).$$

Esto le da a la secuencia finita

$$0, 2, 63, 1308, 12675, 56520, 120960, 120960, 45360, 0, \ldots$$

porque es claramente imposible para el color de la cuadrícula con más de nueve colores distintos. Observar también la entrada de tres colores, que es $P(3) - {3\choose 2} P(2) = 69 - 3\times 2$ es decir, hemos restado los colorantes utilizando dos colores (no hay colorear usando un color y, por tanto, $P(2)$ cuenta colorantes con exactamente dos colores). También se nota que con nueve colores de todas las órbitas tienen el mismo tamaño, es decir, ocho, y de hecho, obtenemos $9!/8 = 45360.$ qué ocurre cuando hay más de nueve colores que podemos recuperar $P(k)$ como sigue:

$$\sum_{q=0}^9 {k\choose q} P'(q).$$

Adenda. El lector puede estar interesado en saber que podemos calcular el OCP para grandes redes, utilizando el código siguiente en junto con el citado enlace:

CUADRADO :=
proc(n)
 opción de recordar;
 local src, la putrefacción, automs, bordes, v2n;

 src := [seq(seq([p, p], p=0..n-1), p=0..n-1)];

 bordes :=
 {seq(seq({[p, q], [p+1, q]},
 p=0..n-2), q=0..n-1),
 seq(seq({[p, q], [p, q+1]},
 p=0..n-1), q=0..n-2)};

 rot := v -> [v[2], n-1-v[1]];

 automs :=
 [src, # identidad
 mapa(rot, src), # 90 grados
 mapa(v -> rot(rot(v)), src), # 180 grados
 mapa(v -> rot(rot(rot(v))), src), # 270 grados

 mapa(v -> [n-1-v[1], v[2]], src), # flip horizontal
 mapa(v -> [v[1], n-1-v[2]], src), # vertical flip

 mapa(v -> rot([n-1-v[1], v[2]]),
 src), # el aumento de diagonal
 mapa(v -> rot(rot(rot([n-1-v[1], v[2]]))),
 src)]; # cayendo en diagonal

 v2n :=
 [seq(seq([p, q] = 1 + p*n + p, q=0..n-1), p=0..n-1)];

 [n*n, subs(v2n, bordes), subs(v2n, automs)];
end;

Obtenemos para un cuatro por cuatro de la OCP

$$1/8\,{k}^{16}-3\,{k}^{15}+{\frac {69\,{k}^{14}}{2}} -{\frac {2015\,{k}^{13}}{8}}+{\frac {10437\,{k}^{12}}{8}} \\-{\frac {20307\,{k}^{11}}{4}}+15333\,{k}^{10}-{\frac {292907\,{k}^{9}}{8}} -{\frac {848501\,{k}^{7}}{8}}+{\frac {1023195\,{k}^{6}}{8}} \\-{\frac {240539\,{k}^{5}}{2}}+{\frac {557915\,{k}^{8}}{8}} -{\frac {8807\,k}{4}}+{\frac {112831\,{k}^{2}}{8}} +{\frac {683997\,{k}^{4}}{8}}-{\frac {347485\,{k}^{3}}{8}}$$

con la secuencia de

$$0, 1, 1155, 759759, 103786510, 4767856260, 107118740001, \ldots$$

Obtenemos un cinco por cinco el OCP

$$1/8\,{k}^{25}+{\frac {69997383\,{k}^{17}}{8}}-5\,{k}^{24} +{\frac {195\,{k}^{23}}{2}}-1233\,{k}^{22}+{\frac {45399\,{k}^{21}}{4}} \\-80919\,{k}^{20}+{\frac {928545\,{k}^{19}}{2}} -{\frac {17590911\,{k}^{18}}{8}}-{\frac {118477969\,{k}^{16}}{4}} +{\frac {172111059\,{k}^{15}}{2}} \\-{\frac {1726958987\,{k}^{14}}{8}} +{\frac {3754019329\,{k}^{13}}{8}}-{\frac {1770719251\,{k}^{12}}{2}} \\+{\frac {5797425049\,{k}^{11}}{4}}-2053661272\,{k}^{10} +{\frac {20055169857\,{k}^{9}}{8}}+{\frac {9236896437\,{k}^{7}}{4}} \\-{\frac {6780818949\,{k}^{6}}{4}}+{\frac {8083053959\,{k}^{5}}{8}} -{\frac {20932696169\,{k}^{8}}{8}}+4017958\,k \\-{\frac {145271789\,{k}^{2}}{4}}-{\frac {3768579695\,{k}^{4}}{8}} +{\frac {1292510453\,{k}^{3}}{8}}$$

con la secuencia de

$$0, 2, 76332, 2557101612, 6352711134515, 2747239197568620, \\378972203462839707, \ldots$$