A114495 Number of returns to the x-axis in all hill-free Dyck paths of semilength n (a Dyck path is said to be hill-free if it has no peaks at level 1).

0, 1, 2, 7, 22, 73, 246, 844, 2936, 10334, 36736, 131709, 475714, 1729345, 6322534, 23232616, 85757008, 317839438, 1182341740, 4412949358, 16521076012, 62024023306, 233451103612, 880764587512, 3330234867792, 12617475113968

Offset

1,3

Comments

Row sums of A114494.

Self-convolution of A000958. - Sergio Falcon, Oct 28 2008

Removing the initial zeros and setting both offsets to zero, this here is the Catalan transform of A006918. - R. J. Mathar, Jun 29 2009

Links

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

Sergio Falcon, Catalan transform of the K-Fibonacci sequence, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832; see also.

Formula

a(n) = Sum_{k=1..floor(n/2)} k^2*binomial(2*n-2*k, n-2*k)/(n-k).

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

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

D-finite with recurrence 2*(n+2)*a(n) +(-7*n-1)*a(n-1) +2*(-3*n-1)*a(n-2) +(7*n-27)*a(n-3) +2*(2*n-5)*a(n-4)=0. - R. J. Mathar, Jul 26 2022

Example

a(4) = 7 because in the six hill-free Dyck paths of semilength 4, namely
UUD(D)UUD(D), UUDUDUD(D), UUDUUDD(D), UUUDDUD(D), UUUDUDD(D) and UUUUDDD(D), we have altogether 7 returns to the x-axis (shown between parentheses).

Maple

a:=n->sum(k^2*binomial(2*n-2*k, n-2*k)/(n-k), k=1..floor(n/2)): seq(a(n), n=1..30);
# second Maple program:
a:= proc(n) option remember; `if`(n<3, n*(n-1)/2,
      ((105*n^3-286*n^2+123*n+10)*a(n-1)
        +2*(n-1)*(2*n-1)*(15*n+2)*a(n-2))/
      (2*(n-2)*(n+2)*(15*n-13)))
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, Feb 08 2014

Mathematica

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

Prog

(PARI) for(n=1, 25, print1(sum(k=1, floor(n/2), k^2*binomial(2*n-2*k, n-2*k)/(n-k)), ", ")) \\ G. C. Greubel, Jan 31 2017

Crossrefs

Cf. A114494.

Sequence in context: A294012 A293809 A307976 * A137398 A151439 A204218

Adjacent sequences: A114492 A114493 A114494 * A114496 A114497 A114498

Keyword

nonn

Author

Emeric Deutsch, Dec 01 2005

Status

approved