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

1, 1, 1, 2, 2, 3, 4, 6, 9, 13, 21, 31, 50, 78, 123, 200, 315, 517, 831, 1355, 2224, 3620, 5995, 9835, 16291, 27004, 44734, 74625, 124078, 207437, 346765, 580418, 974358, 1634622, 2750502, 4628758, 7800544, 13164287, 22223486, 37579843, 63571333, 107659948, 182479796, 309478532

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.

Links

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

Formula

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

Example

a(5)=3 since we have 3 excursions of length 5, namely UUDDH, HUUDD and UDHUD.

Crossrefs

Cf. A329691, A329692.

Sequence in context: A212264 A174650 A107293 * A329976 A329703 A001611

Adjacent sequences: A329690 A329691 A329692 * A329694 A329695 A329696

Keyword

nonn,walk

Author

Valerie Roitner, Dec 06 2019

Status

approved