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
Keywords
Examples
a(3) = 3 because we have UDUDUD, UUDUDD and UUUDDD, where U=(1,1), D=(1,-1).
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.
Crossrefs
Column 0 of A114486.
Programs
-
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 *) -
PARI
x='x+O('x^50); Vec(2/(1+2*x^2+sqrt(1-4*x))) \\ G. C. Greubel, Mar 17 2017
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