|
| |
|
|
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, 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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,10
|
|
|
COMMENTS
| 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.
Sequence in context: A062243 A128095 A189962 * A161515 A145580 A144219
Adjacent sequences: A097851 A097852 A097853 * A097855 A097856 A097857
|
|
|
KEYWORD
| nonn,tabf
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Aug 31 2004
|
| |
|
|
