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

Comments

Row sums are the Catalan numbers (A000108).

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

T(n,0) = A143363(n)

Links

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

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

Formula

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

Example

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;

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

Crossrefs

Cf. A000108, A014301, A143363.

Sequence in context: A146769 A189610 A172427 * A182823 A210866 A245474

Adjacent sequences: A143359 A143360 A143361 * A143363 A143364 A143365

Keyword

nonn,tabl

Author

Emeric Deutsch, Aug 20 2008

Status

approved