OFFSET
0,2
COMMENTS
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.
LINKS
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.
FORMULA
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.
a(n) = (-1)^n*p_n(-2) where p_n(x) is the n-th polynomial described in A219765.
EXAMPLE
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).
MATHEMATICA
nn = 13; e[x_] := Sum[x^n/(n!*2^Binomial[n, 2]), {n, 0, nn}];
Table[n! 2^Binomial[n, 2], {n, 0, nn}] CoefficientList[Series[1/e[-x]^2, {x, 0, nn}], x]
CROSSREFS
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Dec 23 2020
STATUS
approved