A166296 Number of Dyck paths of semilength n with no UUU's and no DDD's and having no UUDUDD's starting at level 0 (U=(1,1), D=(1,-1)).

1, 1, 2, 3, 6, 12, 26, 57, 128, 291, 670, 1558, 3655, 8639, 20554, 49185, 118301, 285840, 693480, 1688683, 4125882, 10111393, 24849532, 61226546, 151212789, 374271925, 928254590, 2306569185, 5741561804, 14315544330, 35748249574

Offset: 0

Author

Emeric Deutsch, Oct 29 2009

Keywords

• nonn

Examples

			a(3)=3 because we have UDUDUD, UDUUDD, and UUDDUD.
		

Links

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

Crossrefs

Cf. A166295.

Programs

Maple

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

Mathematica

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

PARI

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

Formula

a(n) = A166295(n,0).

G.f.: G=2/[1-z-z^2+2*z^3+sqrt(1-2z-z^2-2z^3+z^4)].

a(n) ~ sqrt(360 + 161*sqrt(5)) * ((3+sqrt(5))/2)^n / (8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 20 2014

Equivalently, a(n) ~ 5^(1/4) * phi^(2*n + 6) / (8*sqrt(Pi)*n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 07 2021

D-finite with recurrence 2*(n+3)*a(n) +(-5*n-9)*a(n-1) -n*a(n-2) +12*(1)*a(n-3) +3*(n-4)*a(n-4) +3*(-n+2)*a(n-6) +(n-3)*a(n-7)=0. - R. J. Mathar, Jul 24 2022