login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)). 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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 21 07:27 EDT 2021. Contains 345358 sequences. (Running on oeis4.)