login
Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UD, HU and DH.
1

%I #10 Dec 18 2019 09:03:26

%S 1,1,1,2,2,3,4,6,10,16,28,48,85,152,273,497,906,1665,3071,5688,10579,

%T 19733,36934,69311,130415,245976,464944,880669,1671249,3177210,

%U 6050204,11539013,22039528,42153222,80727500,154789620,297141407,571029896,1098510150,2115321087,4077127817

%N Number of excursions of length n with Motzkin-steps avoiding the consecutive steps UD, HU 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

%C a(n) is also the number of all Motzkin-excursions of length n-1 avoiding UU, HD and DH.

%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+t^2-sqrt(1-2t-t^2+2t^3+t^4-4t^5+4t^6))/(2t^2(1-t)).

%e a(5)=3 since we have 3 (UD, HU and HD)-avoiding excursions of length 5, namely UUHDD, UHHHD and HHHH.

%e Furthermore we have 3 (UU, HD and DH)-avoiding excursions of length 4, namely UDUD, HHUD and HHHH.

%Y Cf. A329698.

%K nonn,walk

%O 0,4

%A _Valerie Roitner_, Dec 12 2019