A114487 Number of Dyck paths of semilength n having no UUDD's starting at level 0.

1, 1, 1, 3, 10, 31, 98, 321, 1078, 3686, 12789, 44919, 159407, 570704, 2058817, 7476621, 27310345, 100275628, 369886451, 1370066394, 5093778398, 19002602171, 71109895075, 266855940177, 1004045604976, 3786790901401, 14313706230574, 54215799080454

Offset

0,4

Links

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

J.-L. Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.

G. Benkart and T. Halverson, Motzkin Algebras, Eur. J. Comb. 36 (2014) 473-502

Dennis E. Davenport, Louis W. Shapiro, and Leon C. Woodson, A bijection between the triangulations of convex polygons and ordered trees, Integers (2020) Vol. 20, Article #A8.

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+2*z^2+sqrt(1-4*z)).

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

a(n) = Sum_{k=0..n/2} (-1)^k*(k+1)/(2*n-3*k+1)*binomial(2*n-3*k+1, n-2*k). - Ira M. Gessel, Jun 16 2018

D-finite with recurrence (n+1)*a(n) +3*(-n+1)*a(n-1) +2*(-2*n+1)*a(n-2) +(n+1)*a(n-3) +2*(-2*n+1)*a(n-4)=0. - R. J. Mathar, Nov 13 2020

Example

a(3) = 3 because we have UDUDUD, UUDUDD and UUUDDD, where U=(1,1), D=(1,-1).

Maple

G:=2/(1+2*z^2+sqrt(1-4*z)): Gser:=series(G, z=0, 33): 1, seq(coeff(Gser, z^n), n=1..30);

Mathematica

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

Prog

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

Crossrefs

Column 0 of A114486.

Sequence in context: A100058 A002160 A214839 * A017934 A005510 A005725

Adjacent sequences: A114484 A114485 A114486 * A114488 A114489 A114490

Keyword

nonn

Author

Emeric Deutsch, Nov 30 2005

Status

approved