A372395 Total number of acyclic orientations in all complete multipartite graphs K_lambda, where lambda ranges over all partitions of n.

1, 1, 3, 11, 65, 411, 3535, 31081, 337185, 3846557, 50329253, 691740489, 10725769171, 172411994899, 3050277039465, 56428854605627, 1124781474310649, 23349607769846667, 518744693882444419, 11949343411110856153, 291921874093876965453, 7395266131906154621501

Offset: 0

Author

Alois P. Heinz, Apr 29 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..333
• 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 A372396.

Cf. A000041, A267383, A372254, A372261, A372326, A370613.

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

Mathematica

g[n_] := g[n] = If[n == 0, 1, Sum[Expand[x*g[n - j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
b[t_, n_, i_] := b[t, n, i] = If[n == 0, t!*(-1)^t, If[i < 1, 0, b[t, n, i - 1] + Sum[Coefficient[g[i], x, m]*b[t + m, n - i, Min[n - i, i]], {m, 0, i}]]];
a[n_] := Abs[b[0, n, n]];
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Jul 24 2024, after Alois P. Heinz *)