cp's OEIS Frontend

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.

%I A372396 #30 Apr 30 2024 18:44:25
%S A372396 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,
%T A372396 384,426,504,600,720,1,64,454,486,1066,1374,1536,1902,2286,2616,3000,
%U A372396 3216,3720,4320,5040,1,128,1394,1458,4718,5658,6144,6902,10554,12090
%N 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.
%C A372396 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 A372396 Alois P. Heinz, <a href="/A372396/b372396.txt">Rows n = 0..28, flattened</a>
%H A372396 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 A372396 Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>
%H A372396 Wikipedia, <a href="https://en.wikipedia.org/wiki/Multipartite_graph">Multipartite graph</a>
%F A372396 T(n,A000041(n)) = A000142(n).
%F A372396 T(n,A000041(n)-1) = A001563(n-1) for n>=2.
%e A372396 Triangle T(n,k) begins:
%e A372396   1;
%e A372396   1;
%e A372396   1,  2;
%e A372396   1,  4,   6;
%e A372396   1,  8,  14,  18,  24;
%e A372396   1, 16,  46,  54,  78,  96, 120;
%e A372396   1, 32, 146, 162, 230, 330, 384, 426, 504, 600, 720;
%e A372396   ...
%p A372396 g:= proc(n) option remember; `if`(n=0, 1, add(
%p A372396       expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
%p A372396     end:
%p A372396 h:= proc() option remember; local q, l, b; q, l, b:= -1, args,
%p A372396       proc(n, j) option remember; `if`(j=1, mul(q-i, i=0..n-1)*
%p A372396         (q-n)^l[1], add(b(n+m, j-1)*coeff(g(l[j]), x, m), m=0..l[j]))
%p A372396       end; abs(b(0, nops(l)))
%p A372396     end:
%p A372396 b:= proc(n, i, l) `if`(n=0 or i=1, [h([l[], 1$n, 0])],
%p A372396      [b(n-i, min(n-i, i), [l[], i])[], b(n, i-1, l)[]])
%p A372396     end:
%p A372396 T:= n-> sort(b(n$2, []))[]:
%p A372396 seq(T(n), n=0..10);
%Y A372396 Columns k=1-3 give: A000012, A011782 (for n>=2), A027649(n-2) (for n>=4).
%Y A372396 Row sums give A372395.
%Y A372396 Cf. A000041, A000142, A001563, A267383, A372254, A372261, A372326, A370614.
%K A372396 nonn,tabf
%O A372396 0,4
%A A372396 _Alois P. Heinz_, Apr 29 2024