login
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
OFFSET
0,3
COMMENTS
a(n) <= A003024(n).
LINKS
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.
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
KEYWORD
nonn
AUTHOR
Jordan Tirrell, Sep 02 2014
EXTENSIONS
a(11) to a(21) computed by Robert Israel, Sep 02 2014
STATUS
approved