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

1, 1, 1, 2, 1, 1, 2, 5, 1, 1, 4, 6, 9, 1, 1, 4, 19, 12, 14, 1, 1, 8, 24, 53, 20, 20, 1, 1, 8, 62, 78, 116, 30, 27, 1, 1, 16, 80, 250, 190, 220, 42, 35, 1, 1, 16, 184, 382, 735, 390, 379, 56, 44, 1, 1, 32, 240, 1020, 1270, 1785, 714, 609, 72, 54, 1, 1, 32, 512, 1580, 3900, 3390, 3808

Offset: 1

Author

Emeric Deutsch, Aug 20 2008

Keywords

• nonn
• tabl

Comments

Row sums are the Motzkin numbers (A001006).

T(n,0) is the sequence 1,1,2,2,4,4,8,8,16,16,... (A016116).

Sum(k*T(n,k),k=0..n-1) = A143335(n).

Examples

			Triangle starts:
1;
1,1;
2,1,1;
2,5,1,1;
4,6,9,1,1;
4,19,12,14,1,1;
		

Links

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

Crossrefs

Cf. A001006, A016116, A143335.

Programs

Maple

g:=((1-t*z-2*z^2-sqrt((1-t*z)^2-4*z^2*(1-z^2+t*z^2)))*1/2)/(t*z^2): gser:= simplify(series(g,z=0,16)): for n to 12 do P[n]:=sort(coeff(gser,z,n)) end do: for n to 12 do seq(coeff(P[n],t,j),j=0..n-1) end do; # yields sequence in triangular form

Formula

G.f.: g, where g=g(t,z) satisfies tz^2*g^2-(1-tz-2z^2)g+z(1+z)=0.