A114589 Number of hill-free Dyck paths of semilength n+3 and having no peaks at even levels (a hill in a Dyck path is a peak at level 1).

1, 1, 3, 7, 17, 43, 110, 286, 753, 2003, 5376, 14540, 39589, 108427, 298512, 825664, 2293271, 6393539, 17885835, 50191175, 141247519, 398537101, 1127203038, 3195229662, 9076078057, 25830193513, 73643406563, 210312889095

Offset: 0

Author

Emeric Deutsch, Dec 11 2005

Keywords

• nonn

Comments

Column 0 of A114588. The number of hill-free Dyck paths having no peaks at odd level are given by the Riordan numbers (A005043).

From Paul Barry, Jul 05 2009: (Start)

The sequence 1,0,0,1,1,3,7,...

has g.f. ((1+x)*(1+2*x)-sqrt((1+x)*(1-3*x)))/(2*x*(2+2*x+x^2)).

It is the inverse binomial transform of A035929(n+1). (End)

Examples

			a(2)=3 because we have UUUDDUUDDD, UUUDUDUDDD and UUUUUDDDDD, where U=(1,1), D=(1,-1).
		

Links

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

Crossrefs

Cf. A114588, A005043.

Programs

Maple

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

Mathematica

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

PARI

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

Formula

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

a(n) ~ 3^(n+11/2) / (50*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 20 2014

Conjecture: 2*(n+4)*a(n) +2*(-n-1)*a(n-1) +3*(-3*n-4)*a(n-2) +(-8*n-11)*a(n-3) +3*(-n-1)*a(n-4)=0. - R. J. Mathar, Jul 02 2018