A135335 Number of Dyck paths of semilength n having no DDUU's starting at level 2.

1, 1, 2, 5, 13, 36, 106, 327, 1045, 3433, 11529, 39414, 136733, 480180, 1703807, 6099193, 22000823, 79890801, 291808480, 1071403389, 3952020216, 14638293671, 54424065467, 203034222400, 759790586108, 2851348853311

Offset

0,3

Comments

a(n) = A135329(n,0). - Emeric Deutsch, Dec 13 2007

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.

Formula

G.f.: (1-2*C+z*C)/(2*z*C-C*z^2-C-z), where C=(1-sqrt(1-4*z))/(2*z) is the g.f. of the Catalan numbers (A000108). - Emeric Deutsch, Dec 13 2007

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

Conjecture: n*a(n) +(-7*n+6)*a(n-1) +2*(8*n-9)*a(n-2) +6*(-3*n+4)*a(n-3) +3*(3*n-4)*a(n-4) +2*(-2*n+3)*a(n-5)=0. - R. J. Mathar, Jun 17 2016

Example

a(4)=13 because among the 14 (=A000108(4)) Dyck paths of semilength 4 only UUDDUUDD does not qualify.

Maple

g:=(1-2*C+z*C)/(2*z*C-C*z^2-C-z): C:=((1-sqrt(1-4*z))*1/2)/z: gser:=series(g, z=0, 30): seq(coeff(gser, z, n), n=0..25); # Emeric Deutsch, Dec 13 2007

Mathematica

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

Prog

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

Crossrefs

Cf. A000108, A135329.

Sequence in context: A135337 A133365 A370886 * A336989 A066723 A000994

Adjacent sequences: A135332 A135333 A135334 * A135336 A135337 A135338

Keyword

nonn

Author

N. J. A. Sloane, Dec 07 2007

Extensions

Edited and extended by Emeric Deutsch, Dec 13 2007

Status

approved