login
Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UH, HU, HD and DH.
0

%I #11 Jan 30 2020 21:29:18

%S 1,1,2,1,3,1,6,1,15,1,43,1,133,1,430,1,1431,1,4863,1,16797,1,58787,1,

%T 208013,1,742901,1,2674441,1,9694846,1,35357671,1,129644791,1,

%U 477638701,1,1767263191,1,6564120421,1,24466267021,1,91482563641,1,343059613651,1,1289904147325,1

%N Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UH, HU, 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 at (n,0) 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.

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

%F a(n)=1 for n odd, a(n)=C(n)+1 for n>0 even, where C(n) is the n-th Catalan number A000108, and a(0)=1.

%F D-finite with recurrence: +(n+2)*a(n) +2*(-n-1)*a(n-1) +(-3*n+4)*a(n-2) +8*(n-2)*a(n-3) +4*(-n+3)*a(n-4)=0. - _R. J. Mathar_, Jan 09 2020

%e a(4)=3 since we have 3 excursions of length 4, namely UUDD, UDUD and HHHH. More generally, for n=2k > 0 even we have all Dyck paths of semilength k and a path consisting only of horizontal steps H^n. For n odd, we only have the path H^n.

%Y Cf. A000108.

%K nonn,walk

%O 0,3

%A _Valerie Roitner_, Dec 12 2019