login
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

%I #7 Jun 26 2015 11:10:42

%S 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,

%T 78,116,30,27,1,1,16,80,250,190,220,42,35,1,1,16,184,382,735,390,379,

%U 56,44,1,1,32,240,1020,1270,1785,714,609,72,54,1,1,32,512,1580,3900,3390,3808

%N 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.

%C Row sums are the Motzkin numbers (A001006).

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

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

%H Gi-Sang Cheon and Louis W. Shapiro, <a href="http://dx.doi.org/10.1016/j.aml.2007.07.001">Protected points in ordered trees</a>, Appl. Math. Letters, 21, 2008, 516-520.

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

%e Triangle starts:

%e 1;

%e 1,1;

%e 2,1,1;

%e 2,5,1,1;

%e 4,6,9,1,1;

%e 4,19,12,14,1,1;

%p 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

%Y Cf. A001006, A016116, A143335.

%K nonn,tabl

%O 1,4

%A _Emeric Deutsch_, Aug 20 2008