A135334 Number of Dyck paths of semilength n having no UDDU's starting at level 1.

1, 1, 2, 4, 10, 29, 90, 290, 960, 3246, 11164, 38934, 137358, 489341, 1757882, 6360634, 23160528, 84802606, 312041692, 1153271984, 4279311348, 15935808866, 59537435012, 223099337404, 838282693560, 3157706225584

Offset

0,3

Comments

Column 0 of A135328. - Emeric Deutsch, Dec 14 2007

The inverse Catalan transform is 1 followed by A133872. - R. J. Mathar, Mar 20 2009

2-colored Motzkin paths of length n with no peaks at level 1. - José Luis Ramírez Ramírez, Dec 08 2011

Links

Vincenzo Librandi, 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

From Emeric Deutsch, Dec 14 2007: (Start)

a(n) = 2*(Sum_{j=0..floor((n-1)/2)} (-1)^j*(j+1)*binomial(2n-2j-1,n))/(n+1) (n >= 1).

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

Conjecture: 2*(n+1)*a(n) + 2*(1-5n)*a(n-1) + 3*(3n-1)*a(n-2) + 2*(1-2n)*a(n-3) = 0. - R. J. Mathar, Dec 18 2011

a(n) ~ 4^(n+2) / (25 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 12 2014

Example

a(3)=4 because among the 5 (=A000108(3)) Dyck paths of semilength 3 only UUDDUD does not qualify.

Maple

a := n -> 2*(add((-1)^j*(j+1)*binomial(2*n-2*j-1, n), j=0..floor((n-1)/2)))/(n+1): 1, seq(a(n), n=1..25); # Emeric Deutsch, Dec 14 2007
G:=1+z*C^2/(1+z^2*C^2): 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 14 2007

Mathematica

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

Crossrefs

Cf. A000108, A135328.

Sequence in context: A262592 A187255 A148114 * A182486 A000995 A010359

Adjacent sequences: A135331 A135332 A135333 * A135335 A135336 A135337

Keyword

nonn

Author

N. J. A. Sloane, Dec 07 2007

Extensions

Edited and extended by Emeric Deutsch, Dec 14 2007

Status

approved