The OEIS is supported by the many generous donors to the OEIS Foundation.

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
`