A246756 Number of noncrossing acyclic digraphs on n labeled nodes.

1, 1, 3, 25, 335, 5521, 101551, 1998753, 41188543, 877423873, 19166868607, 427008572673, 9664851921407, 221617029447425, 5137323018353407, 120193894356728321, 2834498556258175999, 67307873346885345281, 1607986547852912064511, 38620793453818766774273, 932025198556610269241343, 22588476205782950667427841

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