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

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

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 *)

Crossrefs

Row sums of A372396.

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

Sequence in context: A030226 A309174 A233099 * A132101 A280775 A303341

Adjacent sequences: A372392 A372393 A372394 * A372396 A372397 A372398

Keyword

nonn

Author

Alois P. Heinz, Apr 29 2024

Status

approved