A329698 Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UH, HD and DU.

1, 1, 2, 3, 5, 8, 13, 22, 37, 64, 111, 195, 346, 618, 1114, 2019, 3683, 6753, 12440, 23018, 42750, 79683, 148993, 279407, 525382, 990325, 1870993, 3542241, 6719450, 12769653, 24308665, 46348192, 88501413, 169228912, 324018531, 621159937, 1192189832, 2290699981, 4406021067

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..38.

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+2t^3-2t^4-sqrt(1-2t-t^2+2t^3+t^4-4t^5+4t^6))/(2t^3(1-t)^2).

Example

a(3)=3, since we have the following 3 excursions of length 3: UDH, HUD and HHH.

Crossrefs

Cf. A329695.

Sequence in context: A018152 A293078 A005683 * A173404 A325473 A213710

Adjacent sequences: A329695 A329696 A329697 * A329699 A329700 A329701

Keyword

nonn,walk

Author

Valerie Roitner, Dec 16 2019

Status

approved