|
| |
|
|
A104574
|
|
Sum of trapezoid weights of all Motzkin paths of length n.
|
|
2
|
|
|
|
0, 1, 3, 10, 28, 80, 224, 633, 1793, 5109, 14619, 42003, 121089, 350116, 1014892, 2948429, 8582357, 25024833, 73080783, 213714517, 625756147, 1834282280, 5382370208, 15808450470, 46470788358, 136715063545, 402505866459, 1185835240498, 3495843681868, 10311848123968
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
A Motzkin path is a lattice path starting from (0,0), ending at a point on the x-axis, consisting only of steps U=(1,1), D=(1,-1) and H=(1,0) and never going below the x-axis. Motzkin paths are counted by the Motzkin numbers (A001006).
A trapezoid in a Motzkin path is a factor of the form U^i H^j D^i (i>=1, j>=0), i being the height of the trapezoid. A trapezoid in a Motzkin path w is maximal if, as a factor in w, it is not immediately preceded by a U and immediately followed by a D. The trapezoid weight of a Motzkin path is the sum of the heights of its maximal trapezoids. For example, in the Motzkin path w=UH(UHD)D(UUDD) we have two maximal trapezoids (shown between parentheses) of heights 1 and 2, respectively. The trapezoid weight of w is 1+2=3.
This concept is analogous to the concept of pyramid weight in a Dyck path (see the Denise-Simion paper).
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: [1-z-sqrt(1-2z-3z^2)]/[2(1-z)^2*(1+z)sqrt(1-2z-3z^2)].
D-finite with recurrence n*a(n) +(-4*n+3)*a(n-1) +(n-5)*a(n-2) +2*(4*n-5)*a(n-3) +(-5*n+14)*a(n-4) +(-4*n+7)*a(n-5) +3*(n-3)*a(n-6)=0. - R. J. Mathar, Jul 26 2022
|
|
|
EXAMPLE
|
a(3)=3 because the four Motzkin paths of length 3, namely HHH, H(UD), (UD)H and (UHD), have trapezoid weights 0,1,1 and 1, respectively; the maximal trapezoids are shown between parentheses.
|
|
|
MAPLE
|
G:=(1-z-sqrt(1-2*z-3*z^2))/2/(1-z)^2/(1+z)/sqrt(1-2*z-3*z^2): Gser:=series(G, z=0, 34): seq(coeff(Gser, z^n), n=1..32);
|
|
|
MATHEMATICA
|
Rest[CoefficientList[Series[(1 - x - Sqrt[1 - 2 x - 3 x^2]) / (2 (1 - x)^2 (1 + x) Sqrt[1 - 2 x - 3 x^2]), {x, 0, 40}], x]] (* Vaclav Kotesovec, Mar 21 2014 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
