login
Number of meanders of length n with Dyck-steps avoiding the consecutive steps UDU and DUD.
0

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

%S 1,1,2,2,3,4,6,9,14,21,33,50,79,121,192,296,471,730,1164,1812,2894,

%T 4521,7230,11328,18135,28485,45642,71844,115203,181674,291504,460443,

%U 739212,1169283,1878123,2974574,4779865,7578937,12183300,19337489,31096041,49401526,79465563,126350742

%N Number of meanders of length n with Dyck-steps avoiding the consecutive steps UDU and DUD.

%C The Dyck step set is U=(1,1) and D=(1,-1). A meander is a path starting at (0,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 - t^2 - t^3 + t^4 + t^5 - (1+t)*sqrt(t^8-2*t^6-t^4-2*t^2+1))/(2*t*(t^2+t-1)).

%F D-finite with recurrence: (n+1)*a(n) +(n-2)*a(n-1) -2*n*a(n-2) +(-2*n+3)*a(n-3) +(-n+2)*a(n-4) +(-n+4)*a(n-5) +(-2*n+13)*a(n-6) +2*(-n+9)*a(n-7) +(n-10)*a(n-8) +(n-11)*a(n-9)=0. - _R. J. Mathar_, Jan 27 2020

%e a(5)=4 since we have 4 meanders of length 5, namely UUUUU, UUUUD, UUUDD and UUDDU.

%t CoefficientList[Series[(1 - x - x^2 - x^3 + x^4 + x^5 - (1 + x)*Sqrt[x^8 - 2 x^6 - x^4 - 2 x^2 + 1])/(2 x (x^2 + x - 1)), {x, 0, 43}], x] (* _Michael De Vlieger_, Dec 16 2019 *)

%o (PARI) Vec((1 - x - x^2 - x^3 + x^4 + x^5 - (1+x)*sqrt(x^8-2*x^6-x^4-2*x^2+1+O(x^40)))/(2*x*(x^2+x-1))) \\ _Andrew Howroyd_, Dec 20 2019

%Y Cf. A004148, which counts Dyck paths (excursions) avoiding the same consecutive steps.

%K nonn,walk

%O 0,3

%A _Valerie Roitner_, Dec 16 2019