A329695 Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UD, HU and DH.

1, 1, 1, 2, 2, 3, 4, 6, 10, 16, 28, 48, 85, 152, 273, 497, 906, 1665, 3071, 5688, 10579, 19733, 36934, 69311, 130415, 245976, 464944, 880669, 1671249, 3177210, 6050204, 11539013, 22039528, 42153222, 80727500, 154789620, 297141407, 571029896, 1098510150, 2115321087, 4077127817

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

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

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

Cf. A329698.

Sequence in context: A039829 A143588 A284908 * A103599 A032245 A013588

Adjacent sequences: A329692 A329693 A329694 * A329696 A329697 A329698

Keyword

nonn,walk

Author

Valerie Roitner, Dec 12 2019

Status

approved