%I #22 Apr 30 2024 18:45:20
%S 1,1,1,1,4,1,8,1,16,46,1,32,146,330,1,64,454,1066,1374,1,128,1394,
%T 4718,5658,10554,1,256,4246,20266,23118,41506,57054,101502,1,512,
%U 12866,85310,93930,237686,302730,525642,657210,1165104,1,1024,38854,354106,380094
%N 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 into distinct parts; triangle T(n,k), n>=0, k = 1..A000009(n), read by rows.
%C 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.
%H Alois P. Heinz, <a href="/A370614/b370614.txt">Rows n = 0..46, flattened</a>
%H Richard P. Stanley, <a href="http://dx.doi.org/10.1016/0012-365X(73)90108-8">Acyclic Orientations of Graphs</a>, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Multipartite_graph">Multipartite graph</a>
%e Triangle T(n,k) begins:
%e 1;
%e 1;
%e 1;
%e 1, 4;
%e 1, 8;
%e 1, 16, 46;
%e 1, 32, 146, 330;
%e 1, 64, 454, 1066, 1374;
%e 1, 128, 1394, 4718, 5658, 10554;
%e 1, 256, 4246, 20266, 23118, 41506, 57054, 101502;
%e ...
%p g:= proc(n) option remember; `if`(n=0, 1, add(
%p expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
%p end:
%p h:= proc() option remember; local q, l, b; q, l, b:= -1, args,
%p proc(n, j) option remember; `if`(j=1, mul(q-i, i=0..n-1)*
%p (q-n)^l[1], add(b(n+m, j-1)*coeff(g(l[j]), x, m), m=0..l[j]))
%p end; abs(b(0, nops(l)))
%p end:
%p b:= proc(n, i, l) `if`(i*(i+1)/2<n, [], `if`(n=0, [h(l)],
%p [b(n-i, min(n-i, i-1), [l[], i])[], b(n, i-1, l)[]]))
%p end:
%p T:= n-> sort(b(n$2, [0]))[]:
%p seq(T(n), n=0..12);
%Y Columns k=1-2 give: A000012, A011782 (for n>=3).
%Y Row sums give A370613.
%Y Cf. A000009, A267383, A372254, A372261, A372326, A372396.
%K nonn,tabf
%O 0,5
%A _Alois P. Heinz_, Apr 30 2024