cp's OEIS Frontend

A370613 Total number of acyclic orientations in all complete multipartite graphs K_lambda, where lambda ranges over all partitions of n into distinct parts.

%I A370613 #16 Apr 30 2024 18:46:10
%S A370613 1,1,1,5,9,63,509,2959,22453,247949,3080991,28988331,407320739,
%T A370613 5122243495,82583577967,1430027615585,22556817627789,395098668828675,
%U A370613 7979894546677853,154786744386253387,3355612019167352821,78865333300205585345,1769663675666499515751
%N A370613 Total number of acyclic orientations in all complete multipartite graphs K_lambda, where lambda ranges over all partitions of n into distinct parts.
%C A370613 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.
%C A370613 All terms are odd.
%H A370613 Alois P. Heinz, <a href="/A370613/b370613.txt">Table of n, a(n) for n = 0..400</a>
%H A370613 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 A370613 Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>
%H A370613 Wikipedia, <a href="https://en.wikipedia.org/wiki/Multipartite_graph">Multipartite graph</a>
%p A370613 g:= proc(n) option remember; `if`(n=0, 1, add(
%p A370613       expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
%p A370613     end:
%p A370613 b:= proc(t, n, i) option remember; `if`(i*(i+1)/2<n, 0,
%p A370613      `if`(n=0, t!*(-1)^t, add(coeff(g(i), x, m)*
%p A370613       b(t+m, n-i, min(n-i, i-1)), m=0..i)+b(t, n, i-1)))
%p A370613     end:
%p A370613 a:= n-> abs(b(0, n$2)):
%p A370613 seq(a(n), n=0..22);
%Y A370613 Row sums of A370614.
%Y A370613 Cf. A000009, A267383, A372254, A372261, A372326, A372395.
%K A370613 nonn
%O A370613 0,4
%A A370613 _Alois P. Heinz_, Apr 30 2024