A370613 Total number of acyclic orientations in all complete multipartite graphs K_lambda, where lambda ranges over all partitions of n into distinct parts.

1, 1, 1, 5, 9, 63, 509, 2959, 22453, 247949, 3080991, 28988331, 407320739, 5122243495, 82583577967, 1430027615585, 22556817627789, 395098668828675, 7979894546677853, 154786744386253387, 3355612019167352821, 78865333300205585345, 1769663675666499515751

Offset: 0

Author

Alois P. Heinz, Apr 30 2024

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.

All terms are odd.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..400
• 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

Crossrefs

Row sums of A370614.

Cf. A000009, A267383, A372254, A372261, A372326, A372395.

Programs

Maple

g:= proc(n) option remember; `if`(n=0, 1, add(
      expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
    end:
b:= proc(t, n, i) option remember; `if`(i*(i+1)/2 abs(b(0, n$2)):
seq(a(n), n=0..22);