A267384 Number of acyclic orientations of the Turán graph T(n,4).

1, 1, 2, 6, 24, 96, 504, 3216, 24024, 177816, 1538424, 15108216, 165392664, 1793999256, 21693217464, 288019921656, 4154515368024, 59434596913656, 924041894967864, 15469081577068056, 276917744041735704, 4921195271561687256, 93549435117715431864

Offset: 0

Author

Alois P. Heinz, Jan 13 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..450
• 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=4 of A267383.

Formula

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