A097860 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n with k peaks (n>=0, 0<=k<=floor(n/2)).

1, 1, 1, 1, 2, 2, 4, 4, 1, 8, 10, 3, 17, 24, 9, 1, 37, 58, 28, 4, 82, 143, 81, 16, 1, 185, 354, 231, 60, 5, 423, 881, 653, 205, 25, 1, 978, 2204, 1824, 676, 110, 6, 2283, 5534, 5058, 2164, 435, 36, 1, 5373, 13940, 13946, 6756, 1631, 182, 7, 12735, 35213, 38262, 20710

Offset

0,5

Comments

Row sums are the Motzkin numbers (A001006). Column 0 gives A004148.

This triangle is the Motzkin path equivalent to the Narayana numbers (A001263). - Dan Drake, Feb 17 2011

Links

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

Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.

Dan Drake and Ryan Gantner, Generating functions for plateaus in Motzkin paths, J. of the Chungcheong Math. Soc., Vol 25, No. 3, p. 475, August 2012.

Zhuang, Yan. A generalized Goulden-Jackson cluster method and lattice path enumeration, Discrete Mathematics 341.2 (2018): 358-379. Also arXiv: 1508.02793v2.

Formula

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

G.f. has explicit form G(x,t) = (w-sqrt(w^2-4*x^2))/(2*x^2) with w = 1-x+x^2-x^2*t. (Drake and Ganter, Th. 6) - Peter Luschny, Nov 14 2014

Example

Triangle starts:
   1;
   1;
   1,  1;
   2,  2;
   4,  4, 1;
   8, 10, 3;
  17, 24, 9, 1;
  ...
Row n has 1+floor(n/2) terms.
T(4,1)=4 because (UD)HH, H(UD)H, HH(UD) and U(UD)D are the only Motzkin paths of length 4 with 1 peak (here U=(1,1), H=(1,0) and D=(1,-1)); peaks are shown between parentheses.

Maple

eq:=G=1+z*G+z^2*G*(G-1+t):sol:=solve(eq, G): G:=sol[2]: Gser:=simplify(series(G, z=0, 16)): P[0]:=1: for n from 1 to 13 do P[n]:=sort(coeff(Gser, z^n)) od: seq(seq(coeff(t*P[n], t^k), k=1..1+floor(n/2)), n=0..13);
# Alternatively
A097860_row := proc(n) local w, f, p, i;
w := 1-x+x^2-x^2*t; f := (w-sqrt(w^2-4*x^2))/(2*x^2);
p := simplify(coeff(series(f, x, 3+2*n), x, n));
seq(coeff(p, t, i), i=0..iquo(n, 2)) end:
seq(print(A097860_row(n)), n=0..7); # Peter Luschny, Nov 14 2014
# third Maple program:
b:= proc(x, y, t) option remember; expand(`if`(y<0 or y>x, 0,
     `if`(x=0, 1, b(x-1, y, 1)+b(x-1, y-1, 1)*t+b(x-1, y+1, z))))
    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, Feb 01 2019

Mathematica

gf = With[{w = 1 - x + x^2 - x^2*t}, (w - Sqrt[w^2 - 4*x^2])/(2*x^2)];
cx[n_] := cx[n] = SeriesCoefficient[gf, {x, 0, n}];
T[n_, k_] := SeriesCoefficient[cx[n], {t, 0, k}];
Table[T[n, k], {n, 0, 14}, {k, 0, n/2}] // Flatten (* Jean-François Alcover, Dec 04 2017, after Peter Luschny *)

Crossrefs

Cf. A001006, A004148, A001263, A097885.

Sequence in context: A324648 A071511 A119922 * A098979 A071928 A325445

Adjacent sequences: A097857 A097858 A097859 * A097861 A097862 A097863

Keyword

nonn,tabf

Author

Emeric Deutsch, Sep 01 2004

Status

approved