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
Examples
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).
Links
- Alois P. Heinz, Rows n = 0..300, flattened
Programs
-
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 *)
Formula
G.f. G=G(t, z) satisfies z^2*(t+z-tz)G^2-(1-z-z^2+tz^2)*G+1=0.
Extensions
Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 16 2007
Comments