

A370613


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


3



1, 1, 1, 5, 9, 63, 509, 2959, 22453, 247949, 3080991, 28988331, 407320739, 5122243495, 82583577967, 1430027615585, 22556817627789, 395098668828675, 7979894546677853, 154786744386253387, 3355612019167352821, 78865333300205585345, 1769663675666499515751
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



MAPLE

g:= proc(n) option remember; `if`(n=0, 1, add(
expand(x*g(nj))*binomial(n1, j1), 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, ni, min(ni, i1)), m=0..i)+b(t, n, i1)))
end:
a:= n> abs(b(0, n$2)):
seq(a(n), n=0..22);


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



