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
Keywords
Examples
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 |).
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.
Crossrefs
Cf. A119011.
Programs
-
Magma
R
:=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 -
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 *) -
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 -
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
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