login
Triangle read by rows: T(n,k) is number of Dyck paths of semilength n and having k peaks that are not of the form uudd (here u=(1,1), d=(1,-1)).
0

%I #3 Mar 30 2012 17:36:05

%S 1,0,1,1,0,1,1,2,1,1,2,4,4,3,1,4,9,13,9,6,1,8,23,34,35,21,10,1,17,56,

%T 97,111,86,46,15,1,37,138,272,347,321,201,92,21,1,82,344,749,1083,

%U 1111,846,449,169,28,1,185,859,2063,3289,3786,3255,2080,953,289,36,1,423,2154

%N Triangle read by rows: T(n,k) is number of Dyck paths of semilength n and having k peaks that are not of the form uudd (here u=(1,1), d=(1,-1)).

%C Also number of ordered trees with n edges and having k leaves that are endpoints of branches of length 1 (i.e. leaf is child of the root or of a branchnode). Row sums are the Catalan numbers (A000108). Column 0 yields A004148. Sum(kT(n,k),k=0..n)=A097613(n).

%F G.f.=G=G(t, z) satisfies G=1+zG(G-1+t-tz+z).

%e T(4,2)=4 because we have uu(ud)(ud)dd, uudd(ud)(ud), (ud)uudd(ud) and

%e (ud)(ud)uudd (the peaks that are not of the form uudd are shown between parentheses).

%e Triangle begins:

%e 1;

%e 0,1;

%e 1,0,1;

%e 1,2,1,1;

%e 2,4,4,3,1;

%e 4,9,13,9,6,1

%p G:=1/2/z*(1-z^2+z-t*z+z^2*t-sqrt(1-z^2+z^4-2*z^3+4*z^3*t-2*z^4*t+t^2*z^2-2*t^2*z^3+z^4*t^2-2*t*z-2*z)): Gser:=simplify(series(G,z=0,15)): P[0]:=1: for n from 1 to 13 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 13 do seq(coeff(t*P[n],t^k),k=1..n+1) od; # yields sequence in triangular form

%Y Cf. A000108, A004148, A097613.

%K nonn,tabl

%O 0,8

%A _Emeric Deutsch_, Jun 23 2005