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
Keywords
Examples
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).
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.
Crossrefs
Cf. A114494.
Programs
-
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 *) -
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
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
Comments