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

1, 1, 1, 2, 3, 5, 9, 16, 30, 56, 108, 208, 409, 805, 1606, 3211, 6479, 13108, 26691, 54499, 111808, 229983, 474787, 982528, 2039143, 4241187, 8842137, 18469760, 38657209, 81047625, 170212312, 358013615, 754140328, 1590709427, 3359666293, 7104369046, 15040357081, 31875827699

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

Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, preprint, 2019.

Formula

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

Example

a(4)=3 since we have 3 excursions of length 4, namely UUDD, UDUD and HUDH.

Crossrefs

Cf. A329699.

Sequence in context: A050168 A331966 A072176 * A217282 A047061 A136169

Adjacent sequences: A329697 A329698 A329699 * A329701 A329702 A329703

Keyword

nonn,walk

Author

Valerie Roitner, Dec 16 2019

Status

approved