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
Vincenzo Librandi, Table of n, a(n) for n = 1..1000
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.
FORMULA
G.f.: [1-z-sqrt(1-2z-3z^2)]/[2(1-z)^2*(1+z)sqrt(1-2z-3z^2)].
a(n) ~ 3^(n+5/2)/(32*sqrt(Pi*n)). - Vaclav Kotesovec, Mar 21 2014
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
Emeric Deutsch, Mar 16 2005
STATUS
approved