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

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

Author

Alois P. Heinz, Jan 04 2016

Keywords

• nonn

Comments

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.

Links

• 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

Crossrefs

Column k=3 of A267383.

Cf. A182553, A212220, A266695.

Trisection gives A370961.

Programs

Mathematica

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

Formula

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