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,6

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

Links

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

Formula

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

Example

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;

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 *)

Crossrefs

Cf. A001006, A247287.

Sequence in context: A214986 A307133 A218664 * A055587 A137743 A099239

Adjacent sequences: A247283 A247284 A247285 * A247287 A247288 A247289

Keyword

nonn,tabf

Author

Emeric Deutsch, Sep 14 2014

Status

approved