login
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).
5
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
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Dec 01 2005
STATUS
approved