1,2

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.

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

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

a(0) = a(1) = 1; a(n) = n * F(n-1) F(0) = F(1) = 1; F(n) = \sum_{i=1}^{n} a(i) * F(n-i, i) F(0, k) = 1; F(n, 1) = F(n); F(n, k) = \sum_{i=0}^{n} F(i) * F(n-i, k-1)

G.f. A(x) satisfies: a(n) = [x^n] A(x) = [x^(n-1)] (1 + A(x))^n for n>=1; equivalently, a(n) = [x^(n+1)] (n+1)*G(x) for n>=0, where G(x) = SeriesReversion(x/(1 + A(x))) and G(x) is the g.f. of A132070. - Paul D. Hanna (pauldhanna(AT)juno.com), Aug 08 2007

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.

Comment from Paul D. Hanna (pauldhanna(AT)juno.com), Aug 08 2007: G.f. A(x) satisfies a(n) = [x^(n-1)] (1 + A(x))^n as illustrated by:

(1+A)^1 = [(1), 1, 2, 9, 64, 605, 6996, 94556, ...];

(1+A)^2 = [1, (2), 5, 22, 150, 1374, 15539, 206676, ...];

(1+A)^3 = [1, 3, (9), 40, 264, 2346, 25937, 339294, ...];

(1+A)^4 = [1, 4, 14, (64), 413, 3568, 38558, 495848, ...];

(1+A)^5 = [1, 5, 20, 95, (605), 5096, 53840, 680365, ...];

(1+A)^6 = [1, 6, 27, 134, 849, (6996), 72302, 897558, ...];

(1+A)^7 = [1, 7, 35, 182, 1155, 9345, (94556), 1152936, ...]; ...

where only the coefficients of powers (1+A)^m, m=1..7, are shown.

The terms in parenthesis form the initial terms of this sequence.

(PARI) {a(n)=local(G=1+x+2*x^2); for(k=0, n, G=1+x*deriv(serreverse(x/(G+x^2*O(x^n) )))); polcoeff(G, n)} - Paul D. Hanna (pauldhanna(AT)juno.com), Aug 08 2007

Cf. A000108, A110447, A132070.

Sequence in context: A024720 A094100 A067297 this_sequence A059281 A036775 A141209

Adjacent sequences: A113879 A113880 A113881 this_sequence A113883 A113884 A113885

easy,nonn

Marco Kuhlmann (kuhlmann(AT)ps.uni-sb.de), Jan 27 2006