cp's OEIS Frontend

A339934 Number of compatible pairs (C,O) of coloring functions C:V(G) -> {1,2} and acyclic orientations O over all simple labeled graphs G on n nodes.

%I A339934 #24 Jan 22 2025 18:26:03
%S A339934 1,2,10,122,3550,241442,37717630,13335960962,10540951836670,
%T A339934 18433038372948482,70690969784862799870,590117604000940804208642,
%U A339934 10654668783476237855008899070,413773679645643893514443704442882,34396165393184876217278672060698755070,6094509353603648201900616579686281530408962
%N A339934 Number of compatible pairs (C,O) of coloring functions C:V(G) -> {1,2} and acyclic orientations O over all simple labeled graphs G on n nodes.
%C A339934 A pair (C,O) is compatible if for u,v in V(G), when u -> v in the orientation O then C(u) >= C(v).  Note that C is not necessarily a proper coloring of the vertices.
%H A339934 Alois P. Heinz, <a href="/A339934/b339934.txt">Table of n, a(n) for n = 0..78</a>
%H A339934 R. P. Stanley, <a href="https://doi.org/10.1016/j.disc.2006.03.010">Acyclic orientation of graphs</a>, Discrete Math. 5 (1973), 171-178.
%F A339934 Let E(x) = Sum_{n>=0} x^n/(2^binomial(n,2)*n!).  Then Sum_{n>=0} a(n) *  x^n/(2^binomial(n,2)*n!) = 1/E(-x)^2.
%F A339934 a(n) = (-1)^n*p_n(-2) where p_n(x) is the n-th polynomial described in A219765.
%e A339934 a(2) = 10:  There are A003024(2)=3 acyclic orientations of the labeled graphs on 2 nodes.  These are paired with the 2^2=4 colorings for a total of 12 possible pairs.  All except for two of these are compatible. With V(G) = {v_1,v_2} the bad pairs are: v_2 (colored with 0) -> v_1 (colored with 1) and v_1 (colored with 0) -> v_2 (colored with 1).
%p A339934 R:= proc(n) option remember; `if`(n=0, 1, expand(x*add(
%p A339934       binomial(n-1, k)*2^(k*(n-k))*subs(x=x-1, R(k)), k=0..n-1)))
%p A339934     end:
%p A339934 a:= n-> abs(subs(x=-2, R(n))):
%p A339934 seq(a(n), n=0..15);  # _Alois P. Heinz_, Jan 22 2025
%t A339934 nn = 13; e[x_] := Sum[x^n/(n!*2^Binomial[n, 2]), {n, 0, nn}];
%t A339934 Table[n! 2^Binomial[n, 2], {n, 0, nn}] CoefficientList[Series[1/e[-x]^2, {x, 0, nn}], x]
%Y A339934 Cf. A219765, A003024.
%Y A339934 Row sums of A380336.
%K A339934 nonn
%O A339934 0,2
%A A339934 _Geoffrey Critzer_, Dec 23 2020