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,4

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).

Links

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

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

Formula

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

Example

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

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

Crossrefs

Cf. A001006, A016116, A143335.

Sequence in context: A377441 A327722 A334548 * A309522 A336878 A305313

Adjacent sequences: A143361 A143362 A143363 * A143365 A143366 A143367

Keyword

nonn,tabl

Author

Emeric Deutsch, Aug 20 2008

Status

approved