OFFSET
0,3
COMMENTS
The Motzkin step set is U=(1,1), H=(1,0) and D=(1,-1). An excursion is a path starting at (0,0), ending at (n,0) and never crossing the x-axis, i.e., staying at nonnegative altitude.
LINKS
Michael De Vlieger, Table of n, a(n) for n = 0..2743
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, preprint, 2019.
Helmut Prodinger, Motzkin paths of bounded height with two forbidden contiguous subwords of length two, arXiv:2310.12497 [math.CO], 2023.
FORMULA
G.f.: (1 - t + t^3 - sqrt(1-2*t-3*t^2+6*t^3-2*t^4+t^6))/(2*t^2*(1-t)).
G.f. A(x) satisfies: A(x) = x / (1 - x) + 1 / (1 - x^2 * A(x)). - Ilya Gutkovskiy, Nov 03 2021
EXAMPLE
a(4)=4 since we have 4 excursions of length 4, namely: UUDD, UDUD, UDHH and HHHH.
MATHEMATICA
CoefficientList[Series[(1 - x + x^3 - Sqrt[1 - 2 x - 3 x^2 + 6 x^3 - 2 x^4 + x^6])/(2 x^2*(1 - x)), {x, 0, 35}], x] (* Michael De Vlieger, Dec 27 2019 *)
PROG
(PARI) Vec((1 - x + x^3 - sqrt(1-2*x-3*x^2+6*x^3-2*x^4+x^6+O(x^40)))/(2*x^2*(1-x))) \\ Andrew Howroyd, Dec 20 2019
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Valerie Roitner, Dec 16 2019
STATUS
approved