login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A114487
Number of Dyck paths of semilength n having no UUDD's starting at level 0.
2
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
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Nov 30 2005
STATUS
approved