A372084 Number of acyclic orientations of the Turán graph T(n^2,n).

1, 1, 14, 122190, 4154515368024, 1835278052687560517522520, 26375779571296696625528695444035039796080, 25932533306693349690666903275634586837883421559437937952074800, 3259525010466811026507391843042719132975543560928683870154345751824625274129141118944640

Offset: 0

Author

Alois P. Heinz, Apr 17 2024

Keywords

• nonn

Comments

The Turán graph T(n^2,n) is the complete n-partite graph K_{n,...,n}.

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..21
• Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
• Wikipedia, Acyclic orientation
• Wikipedia, Multipartite graph
• Wikipedia, Turán graph

Crossrefs

Main diagonal of A372326.

Cf. A267383.

Formula

a(n) = A267383(n^2,n).