A219765 -id:A219765 - 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.

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

Offset: 0

Geoffrey Critzer, Dec 23 2020

nonn

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.

			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).

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.

Cf. A219765, A003024.

Row sums of A380336.

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

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]

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.

A340798 Square array read by descending antidiagonals. Let G be a simple labeled graph on n nodes. T(n,k) is the number of ways to give G an acyclic orientation and a coloring function C:V(G) -> {1,2,...,k} so that u->v implies C(u) >= C(v) for all u,v in V(G), n >= 0, k >= 0.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 3, 10, 25, 0, 1, 4, 21, 122, 543, 0, 1, 5, 36, 339, 3550, 29281, 0, 1, 6, 55, 724, 12477, 241442, 3781503, 0, 1, 7, 78, 1325, 32316, 1035843, 37717630, 1138779265, 0

Offset: 0

Geoffrey Critzer, Jan 21 2021

			Array begins
  1,     1,      1,       1,       1,       1, ...
  0,     1,      2,       3,       4,       5, ...
  0,     3,     10,      21,      36,      55, ...
  0,    25,    122,     339,     724,    1325, ...
  0,   543,   3550,   12477,   32316,   69595, ...
  0, 29281, 241442, 1035843, 3180484, 7934885, ...
  ...

R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.

Cf. A003024 (column k=1), A339934 (column k=2), A322280, A219765.

nn = 6; e[x_] := Sum[x^n/(n! 2^Binomial[n, 2]), {n, 0, nn}];
Prepend[Table[Table[n! 2^Binomial[n, 2], {n, 0, nn}] CoefficientList[
      Series[1/e[-x]^k, {x, 0, nn}], x], {k, 1, nn}],PadRight[{1}, nn + 1]] // Transpose // Grid

Let E(x) = Sum_{n>=0} x^n/(n!*2^binomial(n,2)). Then Sum_{n>=0} T(n,k)*x^n/(n!*2^binomial(n,2)) = 1/E(-x)^k.

T(n,k) = (-1)^n p_n(-k) where p_n is the n-th polynomial described in A219765.

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula