A118974 Sum of the lengths of the first descents in all hill-free Dyck paths of semilength n (a hill in a Dyck path is a peak at level 1).
0, 0, 2, 4, 11, 31, 94, 298, 977, 3283, 11243, 39087, 137569, 489171, 1754596, 6340756, 23063731, 84372061, 310216081, 1145748061, 4248861631, 15814069951, 59054807821, 221197379221, 830819449003, 3128511421663, 11808294045071, 44666151392095, 169294875129839
Offset: 0
Keywords
Examples
a(4)=11 because in the hill-free Dyck paths of semilength 4, namely uu(dd)uudd, uu(d)uuddd, uu(d)ududd, uuu(dd)udd, uuu(d)uddd and uuuu(dddd), the sum of the lengths of the first descents (shown between parentheses) is 2+1+1+2+1+4=11.
Links
- G. C. Greubel, Table of n, a(n) for n = 0..1000
- Emeric Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
Programs
-
Maple
F:=(1-sqrt(1-4*z))/z/(3-sqrt(1-4*z)): C:=(1-sqrt(1-4*z))/2/z: g:=series(z^2*C*F*(1+C-z*C)/(1-z),z=0,32): seq(coeff(g,z,n),n=0..28);
-
Mathematica
CoefficientList[Series[x^2*(1-Sqrt[1-4*x])/2/x*(1-Sqrt[1-4*x])/x/(3-Sqrt[1-4*x])*(1+(1-Sqrt[1-4*x])/2/x-x*(1-Sqrt[1-4*x])/2/x)/(1-x), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *) -
PARI
my(x='x+O('x^50)); concat([0,0], Vec(x^2*(1-sqrt(1-4*x))/2/x*(1-sqrt(1-4*x))/x/(3-sqrt(1-4*x))*(1+(1-sqrt(1-4*x))/2/x-x*(1-sqrt(1-4*x))/2/x)/(1-x))) \\ G. C. Greubel, Mar 18 2017
Formula
a(n) = Sum_{k=1,..,n} k*A118972(n,k).
G.f.: z^2*C*F*(1+C-z*C)/(1-z), where F = (1-sqrt(1-4*z))/(z*(3-sqrt(1-4*z))) and C = (1-sqrt(1-4*z))/(2*z) is the Catalan function.
a(n) ~ 17*4^n/(27*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 20 2014
Conjecture: 2*(n+1)*(17*n^2-65*n+60)*a(n) -3*(3*n-4)*(17*n^2-48*n+15)*a(n-1) +3*(17*n^3-82*n^2+121*n-60)*a(n-2) +2*(2*n-5) *(17*n^2-31*n+12) *a(n-3)=0. - R. J. Mathar, Jun 22 2016