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

1, 1, 2, 2, 3, 4, 6, 9, 14, 21, 33, 50, 79, 121, 192, 296, 471, 730, 1164, 1812, 2894, 4521, 7230, 11328, 18135, 28485, 45642, 71844, 115203, 181674, 291504, 460443, 739212, 1169283, 1878123, 2974574, 4779865, 7578937, 12183300, 19337489, 31096041, 49401526, 79465563, 126350742

Offset

0,3

Comments

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.

Links

Table of n, a(n) for n=0..43.

Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, preprint, 2019.

Formula

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)).

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

Example

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

Mathematica

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 *)

Prog

(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

Crossrefs

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

Sequence in context: A107293 A329693 A329976 * A001611 A214448 A039829

Adjacent sequences: A329700 A329701 A329702 * A329704 A329705 A329706

Keyword

nonn,walk

Author

Valerie Roitner, Dec 16 2019

Status

approved