login
A372396
Triangle T(n,k) in which row n lists in increasing order the number of acyclic orientations of complete multipartite graphs K_lambda, where lambda is a partition of n; triangle T(n,k), n>=0, k = 1..A000041(n), read by rows.
3
1, 1, 1, 2, 1, 4, 6, 1, 8, 14, 18, 24, 1, 16, 46, 54, 78, 96, 120, 1, 32, 146, 162, 230, 330, 384, 426, 504, 600, 720, 1, 64, 454, 486, 1066, 1374, 1536, 1902, 2286, 2616, 3000, 3216, 3720, 4320, 5040, 1, 128, 1394, 1458, 4718, 5658, 6144, 6902, 10554, 12090
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.
LINKS
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
FORMULA
T(n,A000041(n)) = A000142(n).
T(n,A000041(n)-1) = A001563(n-1) for n>=2.
EXAMPLE
Triangle T(n,k) begins:
1;
1;
1, 2;
1, 4, 6;
1, 8, 14, 18, 24;
1, 16, 46, 54, 78, 96, 120;
1, 32, 146, 162, 230, 330, 384, 426, 504, 600, 720;
...
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:
h:= proc() option remember; local q, l, b; q, l, b:= -1, args,
proc(n, j) option remember; `if`(j=1, mul(q-i, i=0..n-1)*
(q-n)^l[1], add(b(n+m, j-1)*coeff(g(l[j]), x, m), m=0..l[j]))
end; abs(b(0, nops(l)))
end:
b:= proc(n, i, l) `if`(n=0 or i=1, [h([l[], 1$n, 0])],
[b(n-i, min(n-i, i), [l[], i])[], b(n, i-1, l)[]])
end:
T:= n-> sort(b(n$2, []))[]:
seq(T(n), n=0..10);
CROSSREFS
Columns k=1-3 give: A000012, A011782 (for n>=2), A027649(n-2) (for n>=4).
Row sums give A372395.
Sequence in context: A220226 A181854 A109822 * A274292 A359670 A114192
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Apr 29 2024
STATUS
approved