login
Number of excursions of length n with Motzkin-steps consisting only of consecutive steps UH, UD, HD and DH.
2

%I #8 Jul 20 2024 12:30:38

%S 1,1,1,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

%T 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

%U 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

%N Number of excursions of length n with Motzkin-steps consisting only of consecutive steps UH, UD, HD and DH.

%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 on the x-axis and never crossing the x-axis, i.e., staying at nonnegative altitude.

%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 <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (1).

%F G.f.: 1 + t + t^2 + 2t^3 + t^4.

%e We only have the following six excursions of this type: the empty walk, H, UD, UDH, UHD and UHDH.

%Y Cf. A329670, A329677, A329678 (other Motzkin excursions avoiding certain consecutive steps such that the sequence counting them has growth rate zero).

%K nonn,walk,easy

%O 0,4

%A _Valerie Roitner_, Dec 16 2019