|
|
A035101
|
|
E.g.f. x*(c(x/2)-1)/(1-2*x), where c(x) = g.f. for Catalan numbers A000108.
|
|
6
|
|
|
0, 1, 9, 87, 975, 12645, 187425, 3133935, 58437855, 1203216525, 27125492625, 664761133575, 17600023616175, 500706514833525, 15234653491682625, 493699195087473375, 16977671416936605375, 617528830880480644125, 23687738668934964248625
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
2nd column of triangular array A035342 whose first column is given by A001147(n), n >= 1. Recursion: a(n) = 2*n*a(n-1)+ A001147(n-1), n >= 2, a(1)=0.
a(n) gives the number of organically labeled forests (sets) with two rooted ordered trees with n non-root vertices. See the example a(3)=9 given in A035342. Organic labeling means that the vertex labels along the (unique) path from the root to any of the leaves (degree 1, non-root vertices) is increasing. - Wolfdieter Lang, Aug 07 2007
a(n), n>=2, enumerates unordered n-vertex forests composed of two plane (ordered) ternary (3-ary) trees with increasing vertex labeling. See A001147 (number of increasing ternary trees) and a D. Callan comment there. For a picture of some ternary trees see a W. Lang link under A001764.
a(n) is the number of linear chord diagrams on 2n vertices with one marked chord such that exactly 1 of the remaining n-1 chords are contained within the marked chord, see [Young]. - Donovan Young, Aug 11 2020
|
|
LINKS
|
|
|
FORMULA
|
a(n) = n!*A008549(n-1)/2^(n-1) = n!(4^(n-1)-binomial(2*n, n)/2)/2^(n-1).
a(n) = -2*(n-1)*(2*n-3)*a(n-2)+(4*n-3)*a(n-1). - Robert Israel, Sep 11 2015
|
|
EXAMPLE
|
a(2)=1 for the forest: {r1-1, r2-2} (with root labels r1 and r2). The order between the components of the forest is irrelevant (like for sets).
a(3)=9 increasing ternary 2-forest with n=3 vertices: there are three 2-forests (the one vertex tree together with any of the three different 2-vertex trees) each with three increasing labelings. - Wolfdieter Lang, Sep 14 2007
|
|
MAPLE
|
F:= gfun:-rectoproc({(4*n^2+6*n+2)*a(n)+(-4*n-5)*a(n+1)+a(n+2), a(1)=0, a(2)=1, a(3)=9}, a(n), remember):
|
|
MATHEMATICA
|
Table[Round [n! (4^(n - 1) - Binomial[2 n, n]/2)/2^(n - 1)], {n, 1, 20}] (* Vincenzo Librandi, Sep 12 2015 *)
|
|
PROG
|
(Magma) I:=[0, 1, 9]; [n le 3 select I[n] else - 2*(n-1)*(2*n-3)*Self(n-2)+(4*n-3)*Self(n-1): n in [1..30]]; // Vincenzo Librandi, Sep 12 2015
(PARI) a(n) = n!*(4^(n-1)-binomial(2*n, n)/2)/2^(n-1);
|
|
CROSSREFS
|
Cf. A001147 (m=1 column of A035342). See a D. Callan comment there on the number of increasing ordered rooted trees on n+1 vertices.
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|