A114581 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n having k UDH's starting at level 0 (U=(1,1),H=(1,0),D=(1,-1)).

1, 1, 2, 3, 1, 7, 2, 16, 5, 40, 10, 1, 100, 24, 3, 256, 58, 9, 663, 149, 22, 1, 1741, 386, 57, 4, 4620, 1017, 147, 14, 12376, 2702, 392, 40, 1, 33416, 7248, 1053, 113, 5, 90853, 19590, 2859, 312, 20, 248515, 53318, 7803, 870, 65, 1, 683429, 145984, 21420, 2428

Offset: 0

Author

Emeric Deutsch, Dec 09 2005

Keywords

• nonn
• tabf

Comments

Row n contains 1+floor(n/3) terms. Row sums are the Motzkin numbers (A001006). Column 0 yields A114582. Sum(k*T(n,k),k=0..floor(n/3))=A002026(n-2).

Examples

			T(7,2)=3 because we have (UDH)(UDH)H, H(UDH)(UDH) and (UDH)H(UDH), where U=(1,1),H=(1,0),D=(1,-1) (the UDH's starting at level 0 are shown between parentheses).
Triangle starts:
1;
1;
2;
3,1;
7,2;
16,5;
40,10,1;
		

Crossrefs

Cf. A001006, A114582, A002026.

Programs

Maple

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

Formula

G.f.=2/[1-z-2tz^3+2z^3+sqrt(1-2z-3z^2)].