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

1, 1, 2, 3, 6, 10, 20, 36, 73, 139, 286, 567, 1182, 2412, 5085, 10595, 22551, 47712, 102384, 219131, 473523, 1022557, 2222985, 4834578, 10564962, 23109481, 50730082, 111497080, 245729655, 542263213, 1199263450, 2655664953, 5891312918, 13085197538, 29107452153

Offset

0,3

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

Michael De Vlieger, Table of n, a(n) for n = 0..2742

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

Helmut Prodinger, Motzkin paths of bounded height with two forbidden contiguous subwords of length two, arXiv:2310.12497 [math.CO], 2023.

Formula

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

Example

a(3)=3 since we have the following 3 excursions of length 3: UDH, HUD and HHH.

Mathematica

CoefficientList[Series[(1 - x - x^3 - Sqrt[1 - 2 x - 3 x^2 + 6 x^3 - 2 x^4 + x^6])/(2 x^2 (1 - x)^2), {x, 0, 34}], x] (* Michael De Vlieger, Dec 16 2019 *)

Prog

(PARI) Vec((1 - x - x^3 - sqrt(1-2*x-3*x^2+6*x^3-2*x^4+x^6+O(x^40)))/(2*x^2*(1-x)^2)) \\ Andrew Howroyd, Dec 20 2019

Crossrefs

Cf. A329701.

Sequence in context: A002215 A007562 A345973 * A222855 A171682 A008929

Adjacent sequences: A329699 A329700 A329701 * A329703 A329704 A329705

Keyword

nonn,walk

Author

Valerie Roitner, Dec 16 2019

Status

approved