login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A097854 Triangle read by rows: T(n,k) = number of Motzkin paths of length n and having abscissa of first return (i.e., first down step hitting the x-axis) equal to k (k>0); T(n,0)=1 (accounts for the paths consisting only of level steps). 1
1, 1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 2, 2, 4, 1, 0, 4, 4, 4, 8, 1, 0, 9, 8, 8, 8, 17, 1, 0, 21, 18, 16, 16, 17, 38, 1, 0, 51, 42, 36, 32, 34, 38, 89, 1, 0, 127, 102, 84, 72, 68, 76, 89, 216, 1, 0, 323, 254, 204, 168, 153, 152, 178, 216, 539, 1, 0, 835, 646, 508, 408, 357, 342, 356, 432, 539, 1374 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
0,10
COMMENTS
Row sums are the Motzkin numbers (A001006).
LINKS
FORMULA
G.f.: (1-t*z+t^2*z^2*M(t*z)*M(z) - t^2*z^3*M(t*z)*M(z))/(1-z-t*z+t*z^2), where M(z)=(1-z-sqrt(1-2*z-3*z^2))/(2*z^2) is the g.f. of the Motzkin numbers.
T(n,k) = m(n-k)*Sum_{j=0..k-2} m(j), where m(n) = A001006(n) are the Motzkin numbers.
EXAMPLE
Triangle starts:
1;
1, 0;
1, 0, 1;
1, 0, 1, 2;
1, 0, 2, 2, 4;
1, 0, 4, 4, 4, 8;
Row n has n+1 terms.
T(5,3)=4 because the Motzkin paths of length 5 and having abscissa of first return equal to 3 are HU(D)HH, HU(D)UD, UH(D)HH and UH(D)UD (first returns to axis shown between parentheses); here U=(1,1), H=(1,0) and D=(1,-1).
MAPLE
G:=(1-t*z+t^2*z^2*M(t*z)*M(z)-t^2*z^3*M(t*z)*M(z))/(1-z-t*z+t*z^2): M:=z->(1-z-sqrt(1-2*z-3*z^2))/2/z^2: Gser:=simplify(series(G, z=0, 14)): P[0]:=1: for n from 1 to 13 do P[n]:=coeff(Gser, z^n) od: seq(seq(coeff(t*P[n], t^k), k=1..n+1), n=0..12); M:=(1-z-sqrt(1-2*z-3*z^2))/2/z^2: Mser:=series(M, z=0, 15): m[0]:=1: for n from 1 to 12 do m[n]:=coeff(Mser, z^n) od: T:=proc(n, k) if k=0 then 1 elif k<=n then m[n-k]*sum(m[j], j=0..k-2) else 0 fi end: TT:=(n, k)->T(n-1, k-1): matrix(11, 11, TT); # generates the triangle:
MATHEMATICA
(* m = MotzkinNumber *) m[0] = 1; m[n_] := m[n] = m[n - 1] + Sum[m[k]*m[n - 2 - k], {k, 0, n - 2}]; t[n_, 0] = 1; t[n_, k_] := m[n - k]*Sum[m[j], {j, 0, k - 2}]; Table[t[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 10 2013 *)
CROSSREFS
Cf. A001006.
Sequence in context: A316658 A189962 A308321 * A161515 A145580 A144219
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Aug 31 2004
EXTENSIONS
Keyword tabf changed to tabl by Michel Marcus, Apr 09 2013
Terms a(75) and beyond from G. C. Greubel, Oct 23 2017
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 08:13 EDT 2024. Contains 371265 sequences. (Running on oeis4.)