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