A114487 - OEIS

%I #43 Jan 31 2024 08:03:34

%S 1,1,1,3,10,31,98,321,1078,3686,12789,44919,159407,570704,2058817,

%T 7476621,27310345,100275628,369886451,1370066394,5093778398,

%U 19002602171,71109895075,266855940177,1004045604976,3786790901401,14313706230574,54215799080454

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

%H G. C. Greubel, <a href="/A114487/b114487.txt">Table of n, a(n) for n = 0..1000</a>

%H J.-L. Baril, <a href="https://doi.org/10.46298/dmtcs.2158">Avoiding patterns in irreducible permutations</a>, Discrete Mathematics and Theoretical Computer Science,  Vol 17, No 3 (2016). See Table 4.

%H G. Benkart and T. Halverson, <a href="https://doi.org/10.1016/j.ejc.2013.09.010">Motzkin Algebras</a>, Eur. J. Comb. 36 (2014) 473-502

%H Dennis E. Davenport, Louis W. Shapiro, and Leon C. Woodson, <a href="http://math.colgate.edu/~integers/u8/u8.Abstract.html">A bijection between the triangulations of convex polygons and ordered trees</a>, Integers (2020) Vol. 20, Article #A8.

%H A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.005">Counting strings in Dyck paths</a>, Discrete Math., 307 (2007), 2909-2924.

%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016.

%F G.f.: 2/(1+2*z^2+sqrt(1-4*z)).

%F a(n) ~ 4^(n+3) / (81*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Mar 20 2014

%F 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

%F 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

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

%p 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);

%t CoefficientList[Series[2/(1+2*x^2+Sqrt[1-4*x]), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Mar 20 2014 *)

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

%Y Column 0 of A114486.

%K nonn

%O 0,4

%A _Emeric Deutsch_, Nov 30 2005