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

%I #15 Oct 24 2023 12:51:07

%S 1,1,2,3,6,10,20,36,73,139,286,567,1182,2412,5085,10595,22551,47712,

%T 102384,219131,473523,1022557,2222985,4834578,10564962,23109481,

%U 50730082,111497080,245729655,542263213,1199263450,2655664953,5891312918,13085197538,29107452153

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

%C 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.

%H Michael De Vlieger, <a href="/A329702/b329702.txt">Table of n, a(n) for n = 0..2742</a>

%H Andrei Asinowski, Cyril Banderier, and Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, preprint, 2019.

%H Helmut Prodinger, <a href="https://arxiv.org/abs/2310.12497">Motzkin paths of bounded height with two forbidden contiguous subwords of length two</a>, arXiv:2310.12497 [math.CO], 2023.

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

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

%t 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 *)

%o (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

%Y Cf. A329701.

%K nonn,walk

%O 0,3

%A _Valerie Roitner_, Dec 16 2019