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

1, 1, 0, 1, 0, 1, 1, 1, 3, 2, 6, 7, 11, 21, 25, 52, 71, 121, 204, 302, 547, 828, 1417, 2333, 3752, 6454, 10344, 17592, 29097, 48292, 81756, 134961, 228740, 381917, 642048, 1084489, 1817732, 3080591, 5185373, 8772149, 14850172, 25098840, 42612096, 72156764, 122552908, 208140274

Offset

0,9

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

Formula

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

Example

a(8)=3 since we have the following 3 excursions of length 8: UUHDDUHD, UHDUUHDD and UUHDUHDD.

Crossrefs

Cf. A329692, A329693.

Sequence in context: A230267 A286226 A269852 * A293204 A273344 A370665

Adjacent sequences: A329688 A329689 A329690 * A329692 A329693 A329694

Keyword

nonn,walk

Author

Valerie Roitner, Dec 06 2019

Status

approved