login
Triangle T(n,k), n>=1, 0<=k<=n^2, read by rows: row n gives the coefficients of the chromatic polynomial of the square grid graph G_(n,n), highest powers first.
28

%I #28 May 01 2017 22:03:12

%S 1,0,1,-4,6,-3,0,1,-12,66,-216,459,-648,594,-323,79,0,1,-24,276,-2015,

%T 10437,-40614,122662,-292883,557782,-848056,1022204,-960627,682349,

%U -346274,112275,-17493,0,1,-40,780,-9864,90798,-647352,3714180,-17590911,69997383

%N Triangle T(n,k), n>=1, 0<=k<=n^2, read by rows: row n gives the coefficients of the chromatic polynomial of the square grid graph G_(n,n), highest powers first.

%C The square grid graph G_(n,n) has n^2 = A000290(n) vertices and 2*n*(n-1) = A046092(n-1) edges. The chromatic polynomial of G_(n,n) has n^2+1 = A002522(n) coefficients.

%H Alois P. Heinz, <a href="/A182368/b182368.txt">Rows n = 1..9, flattened</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ChromaticPolynomial.html">Chromatic Polynomial</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Chromatic_polynomial">Chromatic Polynomial</a>

%e 3 example graphs: o---o---o

%e . | | |

%e . o---o o---o---o

%e . | | | | |

%e . o o---o o---o---o

%e Graph: G_(1,1) G_(2,2) G_(3,3)

%e Vertices: 1 4 9

%e Edges: 0 4 12

%e The square grid graph G_(2,2) is the cycle graph C_4 with chromatic polynomial q^4 -4*q^3 +6*q^2 -3*q => row 2 = [1, -4, 6, -3, 0].

%e Triangle T(n,k) begins:

%e 1, 0;

%e 1, -4, 6, -3, 0;

%e 1, -12, 66, -216, 459, -648, 594, ...

%e 1, -24, 276, -2015, 10437, -40614, 122662, ...

%e 1, -40, 780, -9864, 90798, -647352, 3714180, ...

%e 1, -60, 1770, -34195, 486210, -5421612, 49332660, ...

%e 1, -84, 3486, -95248, 1926585, -30755376, 403410654, ...

%e 1, -112, 6216, -227871, 6205479, -133865298, 2382122274, ...

%e 1, -144, 10296, -487280, 17169852, -480376848, 11114098408, ...

%t Reverse /@ CoefficientList[Table[ChromaticPolynomial[GridGraph[{n, n}], x], {n, 5}], x] // Flatten (* _Eric W. Weisstein_, May 01 2017 *)

%Y Columns 0, 1 give: A000012, (-1)*A046092(n-1).

%Y Sums of absolute values of row elements give: A080690(n).

%Y Cf. A000290, A002522, A182406, A185442, A193233, A193277, A193283.

%K sign,look,tabf,hard

%O 1,4

%A _Alois P. Heinz_, Apr 26 2012