login
A372395
Total number of acyclic orientations in all complete multipartite graphs K_lambda, where lambda ranges over all partitions of n.
3
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
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
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
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Apr 29 2024
STATUS
approved