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, 34396165393184876217278672060698755070, 6094509353603648201900616579686281530408962
Offset: 0
Keywords
Examples
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).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..78
- R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.
Programs
-
Maple
R:= proc(n) option remember; `if`(n=0, 1, expand(x*add( binomial(n-1, k)*2^(k*(n-k))*subs(x=x-1, R(k)), k=0..n-1))) end: a:= n-> abs(subs(x=-2, R(n))): seq(a(n), n=0..15); # Alois P. Heinz, Jan 22 2025 -
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]
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.
Comments