|
%I #29 Jul 26 2022 15:57:32
%S 0,1,2,7,22,73,246,844,2936,10334,36736,131709,475714,1729345,6322534,
%T 23232616,85757008,317839438,1182341740,4412949358,16521076012,
%U 62024023306,233451103612,880764587512,3330234867792,12617475113968
%N 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).
%C Row sums of A114494.
%C Self-convolution of A000958. - _Sergio Falcon_, Oct 28 2008
%C Removing the initial zeros and setting both offsets to zero, this here is the Catalan transform of A006918. - _R. J. Mathar_, Jun 29 2009
%H G. C. Greubel, <a href="/A114495/b114495.txt">Table of n, a(n) for n = 1..1000</a>
%H Sergio Falcon, <a href="http://www.mathnet.or.kr/mathnet/thesis_file/CKMS-28-4-827-832.pdf">Catalan transform of the K-Fibonacci sequence</a>, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832; see <a href="http://dx.doi.org/10.4134/CKMS.2013.28.4.827">also</a>.
%F a(n) = Sum_{k=1..floor(n/2)} k^2*binomial(2*n-2*k, n-2*k)/(n-k).
%F G.f.: (1 - sqrt(1-4*x))^2/(1 + sqrt(1-4*x) + 2*x)^2.
%F a(n) ~ 5*4^(n+1)/(27*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Mar 20 2014
%F 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
%e a(4) = 7 because in the six hill-free Dyck paths of semilength 4, namely
%e 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).
%p 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);
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n<3, n*(n-1)/2,
%p ((105*n^3-286*n^2+123*n+10)*a(n-1)
%p +2*(n-1)*(2*n-1)*(15*n+2)*a(n-2))/
%p (2*(n-2)*(n+2)*(15*n-13)))
%p end:
%p seq(a(n), n=1..30); # _Alois P. Heinz_, Feb 08 2014
%t 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 *)
%o (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
%Y Cf. A114494.
%K nonn
%O 1,3
%A _Emeric Deutsch_, Dec 01 2005
| 