login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

0,6

COMMENTS

Row n contains 1+floor(n/2) terms. Row sums are the Motzkin numbers (A001006). Sum(k*T(n,k),k=0..floor(n/2))=A005774(n-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.

FORMULA

G.f.: G(t,z) satisfies G = 1+zG+z^2[t(1+zG)+G-1-zG]G.

EXAMPLE

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;

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

CROSSREFS

Cf. A001006, A005774.

Sequence in context: A026499 A242114 A143470 * A257597 A097229 A097862

Adjacent sequences:  A114577 A114578 A114579 * A114581 A114582 A114583

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Dec 09 2005

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 15:22 EDT 2018. Contains 316388 sequences. (Running on oeis4.)