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!)
A246756 Number of noncrossing acyclic digraphs on n labeled nodes. 0
1, 1, 3, 25, 335, 5521, 101551, 1998753, 41188543, 877423873, 19166868607, 427008572673, 9664851921407, 221617029447425, 5137323018353407, 120193894356728321, 2834498556258175999, 67307873346885345281, 1607986547852912064511, 38620793453818766774273, 932025198556610269241343, 22588476205782950667427841 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

a(n) <= A003024(n).

LINKS

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

Marco Kuhlmann, Tabulation of Noncrossing Acyclic Digraphs, arXiv preprint arXiv:1504.04993 [cs.DS], 2015.

M. Kuhlmann, P. Jonsson, Parsing to Noncrossing Dependency Graphs, Transactions of the Association for Computational Linguistics, vol. 3, pp. 559-570, 2015.

MathOverflow, What is the number of noncrossing acyclic digraphs?

Anssi Yli-Jyrä and Carlos Gómez-Rodríguez, Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing, arXiv:1706.03357 [cs.CL], 2017.

FORMULA

G.f.: x*g(x) where (x+1)*g(x)^3+(x^2-2)*g(x)^2+2*x*g(x)+1 = 0. - Robert Israel, Sep 02 2014

MAPLE

S:= series(RootOf((x+1)*y^3+(x^2-2)*y^2+2*x*y+1, y, 1), x, 30):

seq(coeff(S, x, n-1), n=1..30); # Robert Israel, Sep 02 2014

MATHEMATICA

S = Root[(x+1)y^3 + (x^2-2)y^2 + 2x y + 1, y, 2] + O[x]^30;

Prepend[CoefficientList[S, x], 1] (* Jean-François Alcover, Sep 18 2018, after Robert Israel *)

CROSSREFS

Cf. A003024.

Sequence in context: A236268 A181085 A143635 * A023997 A154961 A322760

Adjacent sequences:  A246753 A246754 A246755 * A246757 A246758 A246759

KEYWORD

nonn

AUTHOR

Jordan Tirrell, Sep 02 2014

EXTENSIONS

a(11) to a(21) computed by Robert Israel, Sep 02 2014

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 June 23 13:59 EDT 2021. Contains 345402 sequences. (Running on oeis4.)