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

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

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<n, 0,
     `if`(n=0, t!*(-1)^t, add(coeff(g(i), x, m)*
      b(t+m, n-i, min(n-i, i-1)), m=0..i)+b(t, n, i-1)))
    end:
a:= n-> abs(b(0, n$2)):
seq(a(n), n=0..22);

Crossrefs

Row sums of A370614.

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

Sequence in context: A222536 A222698 A200440 * A347991 A179100 A358966

Adjacent sequences: A370610 A370611 A370612 * A370614 A370615 A370616

Keyword

nonn

Author

Alois P. Heinz, Apr 30 2024

Status

approved