A114500 Number of Dyck paths of semilength n having no UUUDDD's starting at level zero; here U=(1,1), D=(1,-1). Also number of Dyck paths of semilength n having no UUDUDD's starting at level zero.
1, 1, 2, 4, 12, 37, 119, 390, 1307, 4460, 15452, 54207, 192170, 687386, 2477810, 8992007, 32825653, 120460613, 444125661, 1644324767, 6111002752, 22789116600, 85251100275, 319826371389, 1203008722282, 4536009027311, 17141555233270
Offset: 0
Keywords
Examples
a(4)=12 because among the 14 Dyck paths of semilength 4 only UDUUUDDD and UUUDDDUD contain UUUDDD starting at level 0.
Links
- G. C. Greubel, Table of n, a(n) for n = 0..1000
Crossrefs
Cf. A114499.
Programs
-
Maple
C:=(1-sqrt(1-4*z))/2/z: G:=1/(1-z*C+z^3): Gser:=series(G,z=0,35): 1,seq(coeff(Gser,z^n),n=1..30);
-
Mathematica
CoefficientList[Series[1/(1-x*(1-Sqrt[1-4*x])/2/x+x^3), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *) -
PARI
my(x='x+O('x^50)); Vec(2/(1+sqrt(1-4*x)+2*x^3)) \\ Jason Yuen, Sep 09 2024
Formula
G.f.: 1/(1 - z*C + z^3), where C = (1-sqrt(1-4*z))/(2*z) is the Catalan function.
a(n) ~ 4^(n+5)/(1089*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 20 2014
D-finite with recurrence +(n+1)*a(n) +2*(-2*n+1)*a(n-1) +(n+1)*a(n-2) +2*(-2*n+1)*a(n-3) +(n+1)*a(n-5) +2*(-2*n+1)*a(n-6)=0. - R. J. Mathar, Jul 26 2022
Comments