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

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, 97, 111, 86, 46, 15, 1, 37, 138, 272, 347, 321, 201, 92, 21, 1, 82, 344, 749, 1083, 1111, 846, 449, 169, 28, 1, 185, 859, 2063, 3289, 3786, 3255, 2080, 953, 289, 36, 1, 423, 2154

Offset: 0

Author

Emeric Deutsch, Jun 23 2005

Keywords

• nonn
• tabl

Comments

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

Examples

			T(4,2)=4 because we have uu(ud)(ud)dd, uudd(ud)(ud), (ud)uudd(ud) and
(ud)(ud)uudd (the peaks that are not of the form uudd are shown between parentheses).
Triangle begins:
1;
0,1;
1,0,1;
1,2,1,1;
2,4,4,3,1;
4,9,13,9,6,1
		

Crossrefs

Cf. A000108, A004148, A097613.

Programs

Maple

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

Formula

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