Conforme a lo solicitado, utilizando el polinomio $$f(t):= t ( t-1 ) ( {t}^{14}-23\,{t}^{13}+253\,{t}^{12}-1762
\,{t}^{11}+8675\,{t}^{10}-31939\,{t}^{9}+90723\,{t}^{8}-202160\,{t}^{7
}+355622\,{t}^{6}-492434\,{t}^{5}+529770\,{t}^{4}-430857\,{t}^{3}+
251492\,{t}^{2}-94782\,t+17493 )$$ and calculating $f(4)-4f(3)+6f(2)$, la respuesta
es 5969496 por Jonas observación. El 4 es el cuatro grupos diferentes de tres de los colores y el 6 son los pares de dos colores.
Los cálculos para calcular el polinomio cromático de la $4\times 4$ cuadrícula son demasiado complicadas para publicar aquí, sin embargo. Espero que pueda mostrar las ideas detrás de una $3\times 3$ y te puedes imaginar el trabajo que se requiere para hacer el trabajo para la pregunta por la mano.
Mi cromática polinomio de reducción de las normas que figuran en las páginas 24 y 25 de mis notas del curso
El uso de eliminación-contracción en un borde central (1:2 - 2:2), se obtiene que el $g(t) = g_1(t) - g_2(t)$ donde $G_1$ $G_2$ son los siguientes gráficos:
![G1G2]()
A continuación, podemos utilizar la eliminación de la contracción de nuevo, en el extremo opuesto, en tanto $G_1$ $G_2$ y consigue $f(t) = h_1(t) - 2 h_2(t) + h_3(t)$ donde los gráficos son como sigue:
![h123]()
A partir de aquí, se puede utilizar completar la intersección y la máxima de valencia para$H_2$$H_3$, respectivamente, de modo que $h_2(t) = (t-2)^2 \times p(C_6,t) = t \left( t-1 \right) \left( {t}^{4}-5\,{t}^{3}+10\,{t}^{2}-10\,t+5
\right) \left( t-2 \right) ^{2}
$ and $h_3(t) = t \times p(P_3 \copa P_3,t-1) = t \left( t-1 \right) ^{2} \left( t-2 \right) ^{4}$, usando el estándar de los resultados para los polinomios de los ciclos, los caminos y los sindicatos.
Uno más de la eliminación-contracción da $h_1 = t \left( t-1 \right) \left( {t}^{7}-9\,{t}^{6}+36\,{t}^{5}-84\,{t}^{
4}+126\,{t}^{3}-124\,{t}^{2}+76\,t-23 \right)
$
y ponerlos juntos nos da $$g(t) = t \left( t-1 \right) \left( {t}^{7}-11\,{t}^{6}+55\,{t}^{5}-161\,{t}
^{4}+298\,{t}^{3}-350\,{t}^{2}+244\,t-79 \right) $$
Tenga en cuenta que $g(2)=2$ ya que el grafo es bipartito, $g(3) =246$$g(4) =9612$, por lo que hay 8640 colorantes utilizando exactamente 4 colores.
