A329696 Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UH, HU, HD and DH.

1, 1, 2, 1, 3, 1, 6, 1, 15, 1, 43, 1, 133, 1, 430, 1, 1431, 1, 4863, 1, 16797, 1, 58787, 1, 208013, 1, 742901, 1, 2674441, 1, 9694846, 1, 35357671, 1, 129644791, 1, 477638701, 1, 1767263191, 1, 6564120421, 1, 24466267021, 1, 91482563641, 1, 343059613651, 1, 1289904147325, 1

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

Table of n, a(n) for n=0..49.

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

Cf. A000108.

Sequence in context: A119606 A034850 A220377 * A145969 A357985 A140352

Adjacent sequences: A329693 A329694 A329695 * A329697 A329698 A329699

Keyword

nonn,walk

Author

Valerie Roitner, Dec 12 2019

Status

approved