|
| |
|
|
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(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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
