cp's OEIS Frontend

A113882 Number of well-nested drawings of a rooted tree.

%I A113882 #15 Sep 10 2024 16:13:57
%S A113882 1,1,2,9,64,605,6996,94556,1452928,24921765,471091360,9720039120,
%T A113882 217285778700,5230874655578,134929133296972,3713182459524270,
%U A113882 108605754921052880,3364866315332574493,110099293819641466488,3794219154973411079432,137375263325254329836460
%N A113882 Number of well-nested drawings of a rooted tree.
%C A113882 The value a(n) also gives the number of non-crossing partitions on [n] such that (a) each block of the partition is a non-crossing partition itself (recursively) and (b) every partition in this recursion contains at least one singleton block (see A000108). Omitting the factor n in the equation for a(n) gives A110447.
%D A113882 Manuel Bodirsky, Marco Kuhlmann and Mathias Mohl: Well-Nested Drawings as Models of Syntactic Structure, 10th Conference on Formal Grammar and 9th Meeting on Mathematics of Language, Edinburgh, Scotland, UK
%H A113882 Manuel Bodirsky, Marco Kuhlmann and Mathias Mohl: <a href="http://www.ps.uni-sb.de/Papers/abstracts/bodirsky2005wellnested.html">Well-Nested Drawings as Models of Syntactic Structure</a>, 10th Conference on Formal Grammar and 9th Meeting on Mathematics of Language, Edinburgh, Scotland, UK
%F A113882 a(0) = a(1) = 1; a(n) = n * F(n-1), where F(0) = F(1) = 1, F(n) = sum_{i=1}^{n} a(i) * F(n-i, i), where F(0, k) = 1; F(n, 1) = F(n), F(n, k) = sum_{i=0}^{n} F(i) * F(n-i, k-1).
%F A113882 Contribution from _Paul D. Hanna_, Aug 08 2007 (revised Apr 28 2012): (Start)
%F A113882 G.f. A(x) = Sum_{n>=0} a(n)*x^n satisfies:
%F A113882 a(n) = [x^(n-1)] A(x)^n for n>=1;
%F A113882 a(n) = (n+1)*A132070(n+1) for n>=0;
%F A113882 A(x) = x / Series_Reversion(x*G(x)) = G(x/A(x)) where G(x) = A(x*G(x)) is the g.f. of A132070. (End)
%e A113882 a(5)=605 because there are 605 possibilities to form 5 nodes into a rooted tree and order the nodes of this tree such that no two subtrees interleave. Two subtrees t1, t2 interleave if their roots are (tree-)disjoint and there are four nodes l1, r1 from t1 and l2, r2 from t2 such that l1 < l2 < r1 < r2.
%e A113882 Comment from _Paul D. Hanna_, Aug 08 2007 (revised Apr 28 2012): (Start)
%e A113882 Illustrate a(n) = [x^(n-1)] A(x)^n by the following generating method.
%e A113882 Form a table of coefficients in powers of the g.f. A(x):
%e A113882 A(x)^1: [(1), 1, 2, 9, 64, 605, 6996, 94556, ...];
%e A113882 A(x)^2: [1, (2), 5, 22, 150, 1374, 15539, 206676, ...];
%e A113882 A(x)^3: [1, 3, (9), 40, 264, 2346, 25937, 339294, ...];
%e A113882 A(x)^4: [1, 4, 14, (64), 413, 3568, 38558, 495848, ...];
%e A113882 A(x)^5: [1, 5, 20, 95, (605), 5096, 53840, 680365, ...];
%e A113882 A(x)^6: [1, 6, 27, 134, 849, (6996), 72302, 897558, ...];
%e A113882 A(x)^7: [1, 7, 35, 182, 1155, 9345, (94556), 1152936, ...]; ...
%e A113882 then the coefficients along the main diagonal form the initial terms of this sequence. (End)
%o A113882 (PARI) {a(n)=my(G=1+x+2*x^2); for(k=0,n,G=1+x*deriv(serreverse(x/(G+x^2*O(x^n) )))); polcoef(G,n)} \\ _Paul D. Hanna_, Aug 08 2007
%Y A113882 Cf. A000108, A110447, A132070, A361048.
%K A113882 easy,nonn
%O A113882 0,3
%A A113882 Marco Kuhlmann (kuhlmann(AT)ps.uni-sb.de), Jan 27 2006
%E A113882 Initial term added and offset changed to 0 by _Paul D. Hanna_, Apr 28 2012.