login
A212220
Triangle T(n,k), n>=0, 0<=k<=3n, read by rows: row n gives the coefficients of the chromatic polynomial of the complete tripartite graph K_(n,n,n), highest powers first.
6
1, 1, -3, 2, 0, 1, -12, 58, -137, 154, -64, 0, 1, -27, 324, -2223, 9414, -24879, 39528, -33966, 11828, 0, 1, -48, 1064, -14244, 126936, -784788, 3409590, -10329081, 21197804, -27779384, 20648794, -6476644, 0, 1, -75, 2650, -58100, 878200, -9632440, 78681510
OFFSET
0,3
COMMENTS
The complete tripartite graph K_(n,n,n) has 3*n vertices and 3*n^2 = A033428(n) edges. The chromatic polynomial of K_(n,n,n) has 3*n+1 = A016777(n) coefficients.
LINKS
Eric Weisstein's World of Mathematics, Complete Tripartite Graph
FORMULA
T(n,k) = [q^(3*n-k)] Sum_{k,m=0..n} S2(n,k) * S2(n,m) * (q-k-m)^n * Product_{i=0..k+m-1} (q-i) with S2 = A008277.
Sum_{k=0..3n} (-1)^k * T(n,k) = A370961(n). - Alois P. Heinz, May 02 2024
EXAMPLE
2 example graphs: +-------------+
. | +-------+ |
. +-o---o---o |
. \ / \ / \ /
. X X X
. / \ / \ / \
. o---o---o +-o---o---o |
. +-------+ | +-------+ |
. +-------------+
Graph: K_(1,1,1) K_(2,2,2)
Vertices: 3 6
Edges: 3 12
The complete tripartite graph K_(1,1,1) is the cycle graph C_3 with chromatic polynomial q*(q-1)*(q-2) = q^3 -3*q^2 +2*q => [1, -3, 2, 0].
Triangle T(n,k) begins:
1;
1, -3, 2, 0;
1, -12, 58, -137, 154, -64, 0;
1, -27, 324, -2223, 9414, -24879, 39528, ...
1, -48, 1064, -14244, 126936, -784788, 3409590, ...
1, -75, 2650, -58100, 878200, -9632440, 78681510, ...
1, -108, 5562, -180585, 4123350, -70008186, 912054348, ...
...
MAPLE
P:= proc(n) option remember;
expand(add(add(Stirling2(n, k) *Stirling2(n, m)
*mul(q-i, i=0..k+m-1) *(q-k-m)^n, m=0..n), k=0..n))
end:
T:= n-> seq(coeff(P(n), q, 3*n-k), k=0..3*n):
seq(T(n), n=0..6);
MATHEMATICA
P[n_] := P[n] = Expand[Sum[Sum[StirlingS2[n, k] *StirlingS2[n, m]*Product[q - i, {i, 0, k + m - 1}]*(q - k - m)^n, {m, 1, n}], {k, 1, n}]];
T[n_] := Table[Coefficient[P[n], q, 3*n - k], {k, 0, 3*n}];
Array[T, 6] // Flatten (* Jean-François Alcover, May 29 2018, from Maple *)
CROSSREFS
Columns k=0-1 give: A000012, (-1)*A033428.
Row sums and last elements of rows give: A000007.
Row lengths give: A016777.
Sequence in context: A118972 A171224 A270741 * A193233 A145878 A195662
KEYWORD
sign,tabf
AUTHOR
Alois P. Heinz, May 06 2012
EXTENSIONS
T(0,0)=1 prepended by Alois P. Heinz, May 02 2024
STATUS
approved