A143362 Triangle read by rows: T(n,k) is the number of ordered trees with n edges and k protected vertices (0<=k<=n-1). A protected vertex in an ordered tree is a vertex at least 2 edges away from its leaf descendants.

1, 1, 1, 3, 1, 1, 6, 6, 1, 1, 17, 13, 10, 1, 1, 43, 50, 22, 15, 1, 1, 123, 141, 109, 33, 21, 1, 1, 343, 481, 325, 205, 46, 28, 1, 1, 1004, 1491, 1286, 631, 351, 61, 36, 1, 1, 2938, 4929, 4280, 2861, 1101, 562, 78, 45, 1, 1, 8791, 15840, 15662, 10025, 5676, 1783, 855, 97

Offset: 1

Author

Emeric Deutsch, Aug 20 2008

Keywords

• nonn
• tabl

Comments

Row sums are the Catalan numbers (A000108).

Sum(k*T(n,k),k>=0) = A014301(n).

T(n,0) = A143363(n)

Examples

			T(3,2)=1 because among the five ordered trees with 3 edges only the path tree has 2 vertices at least two edges away from the leaf.
Triangle starts:
1;
1,1;
3,1,1;
6,6,1,1;
17,13,10,1,1;
43,50,22,15,1,1;
		

Links

• Gi-Sang Cheon and Louis W. Shapiro, Protected points in ordered trees, Appl. Math. Letters, 21, 2008, 516-520.

Crossrefs

Cf. A000108, A014301, A143363.

Programs

Maple

eq:=G-1/(1-z*G)-z*(t-1)*(G-1)/(1+z-z*G): G:=RootOf(eq,G): Gser:=simplify(series(G-1,z=0,13)): for n to 11 do P[n]:=sort(expand(coeff(Gser,z,n))) end do: for n to 11 do seq(coeff(P[n],t,j),j=0..n-1) end do; # yields sequence in triangular form

Formula

G.f.: G-1, where G=G(t,z) satisfies G = 1/(1-zG) + z(t-1)(G-1)/(1+z-zG).