OFFSET
0,5
COMMENTS
A Motzkin excursion is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), never goes below the x-axis, and terminates at the altitude 0.
A peak is an occurrence of the pattern UD.
A hump is an occurrence of the pattern UHH...HD (the number of Hs in the pattern is not fixed, and can be 0).
Thus every peak is also a hump.
LINKS
Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Algorithmica (2019).
FORMULA
G.f.: -( 4*t^3 + sqrt((1-2*t-3*t^2)*(1-t)^2) + sqrt((1-t-4*t^3)*(1-t)^3) - sqrt((1+t^2)*(1-4*t+5*t^2)) - sqrt((1-2*t)*(1-2*t-t^2)*(1-t^2+2*t^3)) ) / (8*t^2*(1-t)).
a(n) ~ 3^(n + 3/2) / (8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 09 2019
EXAMPLE
For n = 5 the a(5) = 7 paths are UHHHD, UHHDH, HUHHD, HHUHD, HUHDH, UHDHH, UUHDD. In all these paths, 0 peaks and 1 hump.
For n = 0..6, we have only paths with 0 peaks and 1 hump.
For n=7, we have a(n)=34. Among them, 31 paths with 0 peaks and 1 hump, and 3 walks with 2 peaks and 3 humps: UDUDUHD, UDUHDUD, UHDUDUD.
MAPLE
b:= proc(x, y, t, p, h) option remember; `if`(y>x, 0, `if`(x=0,
`if`(p+1=h, 1, 0), `if`(y>0, b(x-1, y-1, 0, irem(p+
`if`(t=1, 1, 0), 2), irem(h+`if`(t=2, 1, 0), 2)), 0)+
b(x-1, y, `if`(t>0, 2, 0), p, h)+b(x-1, y+1, 1, p, h)))
end:
a:= n-> b(n, 0$4):
seq(a(n), n=0..35); # Alois P. Heinz, Jul 04 2019
MATHEMATICA
CoefficientList[Series[-(4 x^3 + Sqrt[(1 - 2 x - 3 x^2)(1 -x)^2] + Sqrt[(1 - x - 4 x^3) (1 - x)^3] - Sqrt[(1 + x^2) (1 - 4 x + 5 x^2)] - Sqrt[(1 - 2 x) (1 - 2 x - x^2) (1 - x^2 + 2 x^3)]) / (8 x^2 (1 - x)), {x, 0, 33}], x] (* Vincenzo Librandi, Jul 09 2019 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Andrei Asinowski, Jul 04 2019
STATUS
approved