A247286 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n having k weak peaks.

1, 1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 8, 7, 4, 1, 1, 16, 17, 11, 5, 1, 1, 32, 41, 30, 16, 6, 1, 1, 64, 98, 82, 48, 22, 7, 1, 1, 128, 232, 220, 144, 72, 29, 8, 1, 1, 256, 544, 581, 423, 233, 103, 37, 9, 1, 1, 512, 1264, 1512, 1216, 738, 356, 142, 46, 10, 1

Offset: 0

Author

Emeric Deutsch, Sep 14 2014

Keywords

• nonn
• tabf

Comments

A weak peak of a Motzkin path is a vertex on the top of a hump. A hump is an upstep followed by 0 or more flatsteps followed by a downstep. For example, the Motzkin path u*duu*h*h*dd, where u=(1,1), h=(1,0), d(1,-1), has 4 weak peaks (shown by the stars).

Row n (n>=1) contains n entries.

Sum of entries in row n is the Motzkin number A001006(n).

Sum(k*T(n,k), 0<=k<=n) = A247287(n).

Examples

			Row 3 is 1,2,1 because the Motzkin paths hhh, hu*d, u*dh, and u*h*d have 0, 1, 1, and 2 weak peaks (shown by the stars).
Triangle starts:
1;
1;
1,1;
1,2,1;
1,4,3,1;
1,8,7,4,1;
		

Links

• Alois P. Heinz, Rows n = 0..141, flattened

Crossrefs

Cf. A001006, A247287.

Programs

Maple

eq := G = 1+z*G+z^2*(G-1/(1-z)+t/(1-t*z))*G: G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 16)): for n from 0 to 14 do P[n] := sort(expand(coeff(Gser, z, n))) end do: 1; for n to 14 do seq(coeff(P[n], t, k), k = 0 .. n-1) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t, c) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, 1, expand(b(x-1, y-1, false, 0)*z^c+b(x-1, y, t,
      `if`(t, c+1, 0))+ b(x-1, y+1, true, 1))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0, false, 0)):
seq(T(n), n=0..14);  # Alois P. Heinz, Sep 14 2014

Mathematica

b[x_, y_, t_, c_] := b[x, y, t, c] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[b[x-1, y-1, False, 0]*z^c + b[x-1, y, t, If[t, c+1, 0]] + b[x-1, y+1, True, 1]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[n, 0, False, 0]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, May 27 2015, after Alois P. Heinz *)

Formula

The g.f. G(t,z) satisfies G = 1 + z*G + z^2*(G - 1/(1-z) + t/(1-t*z))*G.