A097885 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n with k valleys (n>=0, 0<=k<=floor(n/2)-1; a valley is a downstep followed by an upstep).

1, 1, 2, 4, 8, 1, 17, 4, 37, 13, 1, 82, 40, 5, 185, 116, 21, 1, 423, 326, 80, 6, 978, 899, 279, 31, 1, 2283, 2444, 924, 140, 7, 5373, 6578, 2948, 568, 43, 1, 12735, 17576, 9136, 2156, 224, 8, 30372, 46702, 27690, 7777, 1035, 57, 1, 72832, 123568, 82453, 26952, 4422

Offset

0,3

Comments

Also, triangle read by rows: T(n,k) is the number of Motzkin paths of length n and having k double rises (i.e. UU's, where U=(1,1)). E.g. T(5,1)=4 counts HUUDD, UUDDH, UUHDD and UUDHD, where U=(1,1), H=(1,0) and D=(1,-1).

Row sums are the Motzkin numbers (A001006). Column 0 gives A004148.

Links

Alois P. Heinz, Rows n = 0..300, flattened

Formula

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

Example

Triangle starts:
   1;
   1;
   2;
   4;
   8,  1;
  17,  4;
  37, 13, 1;
  ...
Row n (n>=2) has floor(n/2) terms.
T(5,1)=4 counts HU(DU)D, U(DU)DH, U(DU)HD and UH(DU)D (here U=(1,1), H=(1,0) and D=(1,-1); valleys are shown between parentheses).

Maple

eq:=G=1+z*G+z^2*G*(t*(G-1-z*G)+1+z*G): sol:=solve(eq, G): Gser:=simplify(series(sol[1], z=0, 15)): P[0]:=1: for n from 1 to 12 do P[n]:=sort(coeff(Gser, z^n)) od: 1, 1, seq(seq(coeff(t*P[n], t^k), k=1..floor(n/2)), n=0..12);
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, 1, b(x-1, y, 1)+b(x-1, y-1, z)+
            expand(b(x-1, y+1, 1)*t)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Oct 23 2019

Mathematica

(CoefficientList[#, t]& ) /@ CoefficientList[(-(t z^2) + Sqrt[((t-1) z^2 - z + 1)^2 + 4 z^2 (z t - z - t)] + z^2 + z - 1)/(2 z^2 (z t - z - t)) + O[z]^16, z] // Flatten (* Jean-François Alcover, Oct 23 2019 *)

Crossrefs

Cf. A001006, A004148, A097860.

Sequence in context: A097888 A030275 A097874 * A097892 A197282 A215452

Adjacent sequences: A097882 A097883 A097884 * A097886 A097887 A097888

Keyword

nonn,tabf

Author

Emeric Deutsch, Sep 02 2004

Extensions

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 16 2007

Status

approved