OFFSET
0,5
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.
With a(1)=0, the number of Motzkin-like excursions of length n where the level step is H=(3,0). - Alexander Burstein, May 21 2025
In a (UH,HU,HH)-avoiding Motzkin path, an H step can only be preceded or followed by a D step. Therefore, when the path length n is not 1, each run of non-U steps can be partitioned into blocks of D or DH. Thus, each U step can be matched (via tunnels) with a unique block of D or DH. Define the following map recursively on (UH,HU,HH)-avoiding Motzkin paths other than H: an empty path is mapped to itself, and if P is mapped to P' and Q is mapped to Q', then UPDQ is mapped to UP'DQ', and UPDHQ is mapped to P'(HHH)Q', where (HHH) is a level step (3,0). This bijection maps (UH,HU,HH)-avoiding Motzkin paths of length n not equal 1 onto Motzkin-like paths of length n where the level step is (3,0). - Alexander Burstein, May 28 2025
LINKS
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, preprint, 2019.
FORMULA
G.f.: (1+t^3-sqrt(1-4t^2-2t^3+t^6))/(2t^2).
G.f. A(x) satisfies: A(x) = x + 1 / (1 - x^2 * A(x)). - Ilya Gutkovskiy, Nov 03 2021
EXAMPLE
a(5)=3 since we have the following 3 excursions of length 5: UUDDH, UUDHD and UDUDH.
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Valerie Roitner, Dec 16 2019
STATUS
approved