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

Author

N. J. A. Sloane, Dec 07 2007

Keywords

• nonn

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

Examples

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

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.

Crossrefs

Cf. A000108, A135328.

Programs

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

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

Extensions

Edited and extended by Emeric Deutsch, Dec 14 2007