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

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

Links

Table of n, a(n) for n=0..54.

Formula

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

Example

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;

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

Crossrefs

Cf. A001006, A114582, A002026.

Sequence in context: A352062 A263340 A114583 * A328398 A085588 A118008

Adjacent sequences: A114578 A114579 A114580 * A114582 A114583 A114584

Keyword

nonn,tabf

Author

Emeric Deutsch, Dec 09 2005

Status

approved