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.

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

Alois P. Heinz, Rows n = 0..58, flattened

Anatol N. Kirillov, On some quadratic algebras. I 1/2: Combinatorics of Dunkl and Gaudin elements, Schubert, Grothendieck, Fuss-Catalan, universal Tutte and reduced polynomials, SIGMA, Symmetry Integrability Geom. Methods Appl. 12, Paper 002, 172 p. (2016).

Eric Weisstein's World of Mathematics, Complete Tripartite Graph

Wikipedia, Acyclic orientation

Wikipedia, Chromatic Polynomial

Wikipedia, Multipartite 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.

Cf. A008277, A182553, A212221, A370961.

Sequence in context: A118972 A171224 A270741 * A193233 A145878 A195662

Adjacent sequences: A212217 A212218 A212219 * A212221 A212222 A212223

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