A035119 Related to A045720 and A035101.

0, 0, 1, 18, 285, 4680, 82845, 1595790, 33453945, 760970700, 18705542625, 494764058250, 14023390706325, 424278354099600, 13653335491921125, 465794724725079750, 16796514560465264625, 638448710154151396500

Offset

1,4

Comments

3rd column of triangular array A035342. a(n) = (2*n+1)*a(n-1) + A035101(n-1), n >= 3, a(2)=0.

a(n) gives the number of organically labeled forests (sets) with three rooted ordered trees with n non-root vertices. 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. W. Lang, Aug 07 2007.

a(n), n>=3, enumerates unordered n-vertex forests composed of three 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.

Links

Table of n, a(n) for n=1..18.

Formula

a(n) = n!*((n+2)*binomial(2*n, n)/4-3*2^(2*n-3))/(3*2^(n-2)); a(n)= n!*A045720(n-3)/(3*2^(n-2)), n >= 3; E.g.f. (4/3)*(x*c(x/2)*(1-2*x)^(-1/2)/2)^3 = (2*x/3)*((1-x/2)*c(x/2)-1)/(1-2*x)^(3/2), where c(x) = g.f. for Catalan numbers A000108, a(0) := 0.

Example

a(4)=18 for the number of forests (sets) of three increasing labeled rooted trees with 4 non-root vertices and three root labels 0: [(0,4),{(0,1),(0,2)},(0,3)]; [(0,4),{(0,2),(0,1)},(0,3)]; [(0,4),{(0,1),(0,3)},(0,2)]; [(0,4),{(0,3),(0,1)},(0,2)]; [(0,4),{(0,2),(0,3)},(0,1)]; [(0,4),{(0,3),(0,2)},(0,1)]; [(0,4),(0,1,2),(0,3)]; [(0,4),(0,1,3),(0,2)]; [(0,4),(0,2,3),(0,1)]; [{(0,4),(0,1)},(0,2),(0,3)]; [{(0,1),(0,4)},(0,2),(0,3)]; [{(0,4),(0,2)},(0,1),(0,3)]; [{(0,2),(0,4)},(0,1),(0,3)]; [{(0,4),(0,3)},(0,1),(0,2)]; [{(0,3),(0,4)},(0,1),(0,2)]; [(0,1,4),(0,2),(0,3)]; [(0,2,4),(0,1),(0,3)]; [(0,3,4),(0,1),(0,2)].
a(4)=18 increasing ternary 3-forest with n=4 vertices: there are three 3-forests (two one vertex trees together with any of the three different 2-vertex trees) each with six increasing labelings. W. Lang, Sep 14 2007.

Crossrefs

Cf. A000108, A045720, A035101, A035342.

Sequence in context: A249598 A245924 A368526 * A230235 A288959 A294327

Adjacent sequences: A035116 A035117 A035118 * A035120 A035121 A035122

Keyword

easy,nonn

Author

Wolfdieter Lang

Status

approved