A127154 Number of Dyck paths of semilength n and having no UDUD's starting at level 0; here U=(1,1), D=(1,-1).

1, 1, 1, 4, 11, 33, 105, 343, 1148, 3916, 13563, 47571, 168625, 603130, 2174041, 7889617, 28801737, 105696489, 389703392, 1442880489, 5362540760, 19998684400, 74815202891, 280685489717, 1055820378931, 3981166990632, 15045322802905

Offset

0,4

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Formula

G.f.: 2*(1+x)/(1+x+2*x^2+(1+x)*sqrt(1-4*x)).

a(n) = A127153(n,0); column 0 of A127153.

a(n) ~ 25*4^(n+1)/(121*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 20 2014

Conjecture: (n+1)*a(n) +3*a(n-1) +(-11*n+16)*a(n-2) +(-17*n+43)*a(n-3) +(-11*n+28)*a(n-4) +2*(-2*n+7)*a(n-5)=0. - R. J. Mathar, Jun 17 2016

Example

a(3)=4 because we have UDUUDD, UUDDUD, UUDUDD and UUUDDD.
a(4)=11 because among the 14 (=A000108(4)) Dyck paths of semilength 4 the paths that do not qualify are UDUDUDUD, UDUDUUDD and UUDDUDUD.

Maple

g:=2*(1+z)/(1+z+2*z^2+sqrt(1-4*z)+z*sqrt(1-4*z)): gser:=series(g, z=0, 35): seq(coeff(gser, z, n), n=0..30);

Mathematica

CoefficientList[Series[2*(1+x)/(1+x+2*x^2+Sqrt[1-4*x]+x*Sqrt[1-4*x]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)

Prog

(PARI) x='x+O('x^50); Vec(2*(1+x)/(1+x+2*x^2+(1+x)*sqrt(1-4*x))) \\ G. C. Greubel, Mar 19 2017

Crossrefs

Cf. A000108, A127153.

Sequence in context: A099159 A116394 A259442 * A062460 A098324 A327548

Adjacent sequences: A127151 A127152 A127153 * A127155 A127156 A127157

Keyword

nonn

Author

Emeric Deutsch, Feb 27 2007, Dec 13 2007

Status

approved