|
Search: id:A097854
|
|
|
| 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). |
|
+0
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
(list; graph; listen)
|
|
|
OFFSET
|
0,10
|
|
|
COMMENT
|
Row sums are the Motzkin numbers (A001006).
|
|
FORMULA
|
G.f.=(1-tz+t^2*z^2*M(tz)M(z)-t^2*z^3*M(tz)M(z))/(1-z-tz+tz^2), where M(z)=(1-z-sqrt(1-2z-3z^2))/(2z^2) is the g.f. of the Motzkin numbers. T(n, k) = m[n-k]*sum(m[j], j=0..k-2), 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:
|
|
CROSSREFS
|
Cf. A001006.
Adjacent sequences: A097851 A097852 A097853 this_sequence A097855 A097856 A097857
Sequence in context: A058487 A062243 A128095 this_sequence A019591 A091967 A031135
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Aug 31 2004
|
|
|
Search completed in 0.002 seconds
|
