OFFSET

0,4

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

a(n) is also the number of all Motzkin-excursions of length n-1 avoiding UU, HD and DH.

LINKS

Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, preprint, 2019.

FORMULA

G.f.: (1-t+t^2-sqrt(1-2t-t^2+2t^3+t^4-4t^5+4t^6))/(2t^2(1-t)).

EXAMPLE

a(5)=3 since we have 3 (UD, HU and HD)-avoiding excursions of length 5, namely UUHDD, UHHHD and HHHH.

Furthermore we have 3 (UU, HD and DH)-avoiding excursions of length 4, namely UDUD, HHUD and HHHH.

CROSSREFS

KEYWORD

nonn,walk

AUTHOR

Valerie Roitner, Dec 12 2019

STATUS

approved