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

Author

Wolfdieter Lang

Keywords

• easy
• nonn

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.

Examples

			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.

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.