cp's OEIS Frontend

A370614 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.

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