A329694 Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UU, HH and DU.

1, 1, 1, 3, 3, 3, 8, 12, 13, 27, 50, 64, 109, 215, 322, 504, 966, 1616, 2526, 4578, 8115, 13143, 22836, 41162, 69410, 118536, 212498, 369226, 631631, 1119755, 1977612, 3419130, 6014450, 10684128, 18689970, 32807722, 58300072, 102905556, 181031164, 321348824, 570303658, 1007402762

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

Formula

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

Example

a(4)=3 since we have the following 3 excursions of length 4: UHDH, HUHD and HUDH.

Crossrefs

Cf. A248100.

Sequence in context: A346159 A241739 A226509 * A183389 A275530 A180637

Adjacent sequences: A329691 A329692 A329693 * A329695 A329696 A329697

Keyword

nonn,walk

Author

Valerie Roitner, Dec 06 2019

Status

approved