cp's OEIS Frontend

A372395 Total number of acyclic orientations in all complete multipartite graphs K_lambda, where lambda ranges over all partitions of n.

%I A372395 #20 Jul 24 2024 13:22:14
%S A372395 1,1,3,11,65,411,3535,31081,337185,3846557,50329253,691740489,
%T A372395 10725769171,172411994899,3050277039465,56428854605627,
%U A372395 1124781474310649,23349607769846667,518744693882444419,11949343411110856153,291921874093876965453,7395266131906154621501
%N A372395 Total number of acyclic orientations in all complete multipartite graphs K_lambda, where lambda ranges over all partitions of n.
%C A372395 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 A372395 All terms are odd.
%H A372395 Alois P. Heinz, <a href="/A372395/b372395.txt">Table of n, a(n) for n = 0..333</a>
%H A372395 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 A372395 Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>
%H A372395 Wikipedia, <a href="https://en.wikipedia.org/wiki/Multipartite_graph">Multipartite graph</a>
%p A372395 g:= proc(n) option remember; `if`(n=0, 1, add(
%p A372395       expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
%p A372395     end:
%p A372395 b:= proc(t, n, i) option remember; `if`(n=0, t!*(-1)^t,
%p A372395      `if`(i<1, 0, b(t, n, i-1)+add(coeff(g(i), x, m)*
%p A372395         b(t+m, n-i, min(n-i, i)), m=0..i)))
%p A372395     end:
%p A372395 a:= n-> abs(b(0, n$2)):
%p A372395 seq(a(n), n=0..21);
%t A372395 g[n_] := g[n] = If[n == 0, 1, Sum[Expand[x*g[n - j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
%t A372395 b[t_, n_, i_] := b[t, n, i] = If[n == 0, t!*(-1)^t, If[i < 1, 0, b[t, n, i - 1] + Sum[Coefficient[g[i], x, m]*b[t + m, n - i, Min[n - i, i]], {m, 0, i}]]];
%t A372395 a[n_] := Abs[b[0, n, n]];
%t A372395 Table[a[n], {n, 0, 21}] (* _Jean-François Alcover_, Jul 24 2024, after _Alois P. Heinz_ *)
%Y A372395 Row sums of A372396.
%Y A372395 Cf. A000041, A267383, A372254, A372261, A372326, A370613.
%K A372395 nonn
%O A372395 0,3
%A A372395 _Alois P. Heinz_, Apr 29 2024