login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A342113 Number of surjective compatible pairs (C,O), where O is an acyclic orientation of simple labeled graph G on n nodes and C:V(G) -> {1,2,...}. 0
1, 1, 7, 145, 7999, 1103041, 365051647, 281898887425, 497570152386559, 1976049386530790401, 17439288184770966867967, 338596445913833207323643905, 14343481992486219718322674565119 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

A pair (C,O) is a surjective compatible pair if O is an acyclic orientation of the edges of a simple labeled graph G on n nodes, and C is a surjective function from V(G)->{1,2,...k} for some positive integer k such that for all u,v in V(G) if u->v under the orientation then C(u)>= C(v).

LINKS

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

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

FORMULA

Let E(x) = Sum_{n>=0}x^n/(n! 2^Binomial(n,2)).  Then Sum_{n>=0}a_n x^n/(n! 2^Binomial(n,2)) = 1/(2 - E(-x)^-1).

MATHEMATICA

nn = 12; b[n_] := q^Binomial[n, 2] n! /. q -> 2; e[z_] := Sum[z^n/b[n], {n, 0, nn}]; Table[b[n], {n, 0, nn}] CoefficientList[ Series[1/(1 - (1/e[-z] - 1)), {z, 0, nn}], z]

CROSSREFS

Cf. A339934.

Sequence in context: A232363 A102059 A064624 * A211108 A251668 A048935

Adjacent sequences:  A342110 A342111 A342112 * A342114 A342115 A342116

KEYWORD

nonn

AUTHOR

Geoffrey Critzer, Feb 28 2021

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 14:45 EDT 2021. Contains 347668 sequences. (Running on oeis4.)