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

Offset

0,3

Links

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

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

Formula

a(n) = Sum_{k=1,..,n} k*A118972(n,k).

G.f.: z^2*CF(1+C-zC)/(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

Example

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.

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 *)

Prog

(PARI) 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

Crossrefs

Cf. A000957, A118972.

Sequence in context: A274775 A039300 A247333 * A119020 A073191 A173139

Adjacent sequences: A118971 A118972 A118973 * A118975 A118976 A118977

Keyword

nonn

Author

Emeric Deutsch, May 08 2006

Status

approved