A097888 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n having k high humps. (A hump is an upstep followed by 0 or more flatsteps followed by a downstep. A high hump is a hump that starts at a level higher than zero.).

1, 1, 2, 4, 8, 1, 16, 5, 32, 18, 1, 64, 56, 7, 128, 160, 34, 1, 256, 432, 138, 9, 512, 1120, 500, 55, 1, 1024, 2816, 1672, 275, 11, 2048, 6912, 5264, 1205, 81, 1, 4096, 16640, 15808, 4797, 481, 13, 8192, 39424, 45696, 17738, 2471, 112, 1, 16384, 92160, 128000

Offset

0,3

Comments

Row sums are the Motzkin numbers (A001006).

Links

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

Formula

G.f.=G=G(t, z) satisfies tz^2*(1-z)G^2-(1-2*z+tz^2)*G+1-z=0.

Example

Triangle begins:
1;
1;
2;
4;
8,1;
16,5;
32,18,1;
Row n contains floor(n/2) terms.
T(5,1)=5 counts HU(UD)D, U(UD)DH, UH(UD)D, U(UD)HD and U(UHD)D, where U=(1,1), H=(1,0), D=(1,-1) (the high humps are shown between parentheses).

Crossrefs

Cf. A001006.

Sequence in context: A282821 A317495 A317504 * A030275 A097874 A097885

Adjacent sequences: A097885 A097886 A097887 * A097889 A097890 A097891

Keyword

nonn,tabf

Author

Emeric Deutsch, Sep 02 2004

Status

approved