A119012 Number of valleys strictly above the x-axis in all hill-free Dyck paths of semilength n (a hill in a Dyck path is a peak at level 1).

0, 0, 1, 5, 23, 98, 405, 1644, 6604, 26356, 104746, 415155, 1642493, 6490622, 25629581, 101156936, 399151400, 1574818496, 6213255614, 24515233082, 96739530062, 381803092580, 1507141137026, 5950525214360, 23498966702808

Offset

1,4

Links

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

E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

Formula

a(n) = Sum_{k=0,..,n-2} k*A119011(n,k).

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

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

Conjecture: 2*(n-3)*(3*n-2)*(n+2)*a(n) +(-21*n^3+50*n^2-13*n-4)*a(n-1) -2*(n-1) *(2*n-1)*(3*n+1)*a(n-2)=0. - R. J. Mathar, Jun 22 2016

Example

a(4)=5 because in the 6 (=A000957(5)) hill-free Dyck paths of semilength 4, namely UUUUDDDD, UUUD|UDDD, UUD|UUDDD, UUD|UD|UDD, UUUDD|UDD and UUDDUUDD (U=(1,1), D=(1,-1)) we have altogether 5 valleys strictly above the x-axis (indicated by |).

Maple

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

Mathematica

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

Prog

(PARI) x='x+O('x^30); concat([0, 0], Vec(2*(1-3*x-(1-x)*sqrt(1-4*x)) /( (1+2*x+sqrt(1-4*x))^2*sqrt(1-4*x)))) \\ G. C. Greubel, Mar 19 2017
(Magma) R<x>:=PowerSeriesRing(Rationals(), 30); [0, 0] cat Coefficients(R!( 2*(1-3*x-(1-x)*Sqrt(1-4*x))/((1+2*x+ Sqrt(1-4*x))^2 *Sqrt(1-4*x)) )); // G. C. Greubel, Apr 06 2019
(Sage) a=(2*(1-3*x-(1-x)*sqrt(1-4*x)) /( (1+2*x+sqrt(1-4*x))^2* sqrt(1-4*x))).series(x, 30).coefficients(x, sparse=False); a[1:] # G. C. Greubel, Apr 06 2019

Crossrefs

Cf. A119011.

Sequence in context: A109765 A323922 A368835 * A215038 A084615 A181331

Adjacent sequences: A119009 A119010 A119011 * A119013 A119014 A119015

Keyword

nonn

Author

Emeric Deutsch, May 08 2006

Status

approved