A182553 -id:A182553 - cp's OEIS frontend

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

Alois P. Heinz, May 06 2012

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.

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

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

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.

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);

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 *)

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

T(0,0)=1 prepended by Alois P. Heinz, May 02 2024

A266858 Number of acyclic orientations of the Turán graph T(n,3).

Original entry on oeis.org

1, 1, 2, 6, 18, 78, 426, 2286, 15402, 122190, 951546, 8724078, 90768378, 928340190, 10779805722, 138779942046, 1759271695338, 24739709631678, 379578822373866, 5743346972756526, 94864142045862282, 1689637343582548590, 29717468115957434586, 563879701735681033998

Offset: 0

Alois P. Heinz, Jan 04 2016

nonn

An acyclic orientation is an assignment of a direction to each edge such that no cycle in the graph is consistently oriented. Stanley showed that the number of acyclic orientations of a graph G is equal to the absolute value of the chromatic polynomial X_G(q) evaluated at q=-1.

Alois P. Heinz, Table of n, a(n) for n = 0..465
P. J. Cameron, C. A. Glass, R. U. Schumacher, Acyclic orientations and poly-Bernoulli numbers, arXiv:1412.3685 [math.CO], 2014-2018.
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
Wikipedia, Turán graph

Column k=3 of A267383.
Cf. A182553, A212220, A266695.
Trisection gives A370961.

A[n_, k_] := A[n, k] = Module[{b, l, q}, q = -1; l = Join[Array[Floor[ n/k]&, k - Mod[n, k]], Array[Ceiling[n/k]&, Mod[n, k]]]; b[nn_, j_] := b[nn, j] = If[j==1, (q-nn)^l[[1]] Product[q-i, {i, 0, nn-1}], Sum[b[nn + m, j-1] StirlingS2[l[[j]], m], {m, 0, l[[j]]}]]; Abs[b[0, k]]];
a[n_] := A[n, 3];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Aug 20 2018, after Alois P. Heinz *)

a(n) ~ n! / (2*(1 - log(3/2)) * 3^n * (log(3/2))^(n+1)). - Vaclav Kotesovec, Feb 18 2017

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions