A329701 Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UH and HU.

1, 1, 2, 2, 4, 5, 11, 17, 38, 67, 148, 282, 616, 1231, 2674, 5511, 11957, 25162, 54673, 116748, 254393, 549035, 1200429, 2611594, 5730385, 12544520, 27620602, 60766999, 134232576, 296533559, 657000238, 1456401504, 3235647966, 7193884621, 16022254616, 35714681625

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

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

G.f. A(x) satisfies: A(x) = x / (1 - x) + 1 / (1 - x^2 * A(x)). - Ilya Gutkovskiy, Nov 03 2021

Example

a(4)=4 since we have 4 excursions of length 4, namely: UUDD, UDUD, UDHH and HHHH.

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)), {x, 0, 35}], x] (* Michael De Vlieger, Dec 27 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))) \\ Andrew Howroyd, Dec 20 2019

Crossrefs

Cf. A329702.

Sequence in context: A127825 A185100 A103420 * A032258 A153949 A302400

Adjacent sequences: A329698 A329699 A329700 * A329702 A329703 A329704

Keyword

nonn,walk

Author

Valerie Roitner, Dec 16 2019

Status

approved