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.

1, 2, 10, 122, 3550, 241442, 37717630, 13335960962, 10540951836670, 18433038372948482, 70690969784862799870, 590117604000940804208642, 10654668783476237855008899070, 413773679645643893514443704442882

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

Table of n, a(n) for n=0..13.

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

Cf. A219765, A003024.

Sequence in context: A060690 A013038 A005321 * A348876 A092645 A346372

Adjacent sequences: A339931 A339932 A339933 * A339935 A339936 A339937

Keyword

nonn

Author

Geoffrey Critzer, Dec 23 2020

Status

approved