A114580 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n having k ascents (0<=k<=floor(n/2)); an ascent is a maximal string of upsteps.
1, 1, 1, 1, 1, 3, 1, 7, 1, 1, 14, 6, 1, 26, 23, 1, 1, 46, 70, 10, 1, 79, 186, 56, 1, 1, 133, 451, 235, 15, 1, 221, 1025, 825, 115, 1, 1, 364, 2220, 2562, 630, 21, 1, 596, 4634, 7274, 2794, 211, 1, 1, 972, 9396, 19286, 10696, 1456, 28, 1, 1581, 18612, 48450, 36715
Offset: 0
Examples
T(4,1) = 7 because we have HH(U)D, H(U)DH, H(U)HD, (U)DHH, (U)HDH, (U)HHD and (UU)HH, where U=(1,1), H=(1,0), D=(1,-1) (the ascents are shown between parentheses). Triangle begins: 1; 1; 1, 1; 1, 3; 1, 7, 1; 1, 14, 6; 1, 26, 23, 1;
Links
- Alois P. Heinz, Rows n = 0..200, flattened
- Zhuang, Yan. A generalized Goulden-Jackson cluster method and lattice path enumeration, Discrete Mathematics 341.2 (2018): 358-379. Also arXiv: 1508.02793v2.
Programs
-
Maple
G:=1/2*(1-z+z^2-t*z^2-sqrt(1-z^2-2*z+2*z^3-2*z^3*t-2*z^2*t+z^4-2*z^4*t+z^4*t^2))/z^2/(z*t+1-z): Gserz:=simplify(series(G,z=0,18)): P[0]:=1: for n from 1 to 15 do P[n]:=sort(coeff(Gserz,z^n)) od: for n from 0 to 15 do seq(coeff(t*P[n],t^j),j=1..1+floor(n/2)) od; # yields sequence in triangular form # second Maple program: b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0, `if`(x=0, 1, expand(`if`(t, 1, z)*b(x-1, y-1, true) +b(x-1, y+1, false)+b(x-1, y, false)))) end: T:= n->(p->seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0, false)): seq(T(n), n=0..20); # Alois P. Heinz, Mar 11 2014 -
Mathematica
b[x_, y_, t_] := b[x, y, t] = If[y>x || y<0, 0, If[x == 0, 1, Expand[If[t, 1, z]*b[x-1, y-1, True] + b[x-1, y+1, False] + b[x-1, y, False]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[n, 0, False]]; Table[T[n], {n, 0, 20}] // Flatten (* Jean-François Alcover, May 22 2015, after Alois P. Heinz *)
Formula
G.f.: G(t,z) satisfies G = 1+zG+z^2[t(1+zG)+G-1-zG]G.
Comments