|
%I
%S 1,1,1,3,4,7,15,26,50,102,196,392,800,1609,3290,6786,13973,28998,
%T 60469,126295,264945,557594,1176004,2487485,5274110,11204631,23854581,
%U 50881939,108715072,232671125,498724913,1070525053,2301048452,4952319218,10671175097,23020363339
%N Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UU and HH.
%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.
%C a(n) also counts excursions avoiding the consecutive steps HH and DD. This can easily be seen by time reversal.
%C a(n) also counts excursions avoiding the consecutive steps HH and DU.
%F G.f.: (1/2)*(1 - t^3 - t^2 - sqrt(t^6 + 2*t^5 - 3*t^4 - 6*t^3 - 2*t^2 + 1))/t^3.
%F a(0) = a(1) = a(2) = 1; a(n) = a(n-2) + a(n-3) + Sum_{k=0..n-3} a(k) * a(n-k-3). - _Ilya Gutkovskiy_, Nov 09 2021
%e a(3)=3 as there are 3 excursions of length 3, namely: UDH, UHD and HUD.
%Y See also A329667, A329668, A329669, which count meanders with the same step set and forbidden consecutive steps "UU and HH", "HH and DU" as well as "HH and DD" respectively.
%K nonn,walk
%O 0,4
%A _Valerie Roitner_, Nov 19 2019
|
