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

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

FORMULA

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

a(n)=1 for n odd, a(n)=C(n)+1 for n>0 even, where C(n) is the n-th Catalan number A000108, and a(0)=1.

D-finite with recurrence: +(n+2)*a(n) +2*(-n-1)*a(n-1) +(-3*n+4)*a(n-2) +8*(n-2)*a(n-3) +4*(-n+3)*a(n-4)=0. - R. J. Mathar, Jan 09 2020

EXAMPLE

a(4)=3 since we have 3 excursions of length 4, namely UUDD, UDUD and HHHH. More generally, for n=2k > 0 even we have all Dyck paths of semilength k and a path consisting only of horizontal steps H^n. For n odd, we only have the path H^n.

CROSSREFS

KEYWORD

nonn,walk

AUTHOR

Valerie Roitner, Dec 12 2019

STATUS

approved