login
Number of peaks in all hill-free Dyck paths of semilength n (a Dyck path is hill-free if it has no peaks at level 1).
3

%I #31 Sep 09 2024 22:43:02

%S 0,0,1,3,12,45,171,651,2488,9540,36690,141482,546864,2118207,8219967,

%T 31952115,124389552,484908408,1892657934,7395597354,28928182440,

%U 113260606074,443827115886,1740592240638,6831289801872,26829201570600

%N Number of peaks in all hill-free Dyck paths of semilength n (a Dyck path is hill-free if it has no peaks at level 1).

%H G. C. Greubel, <a href="/A114515/b114515.txt">Table of n, a(n) for n = 0..1000</a>

%H Sergi Elizalde, <a href="https://arxiv.org/abs/2008.05669">Symmetric peaks and symmetric valleys in Dyck paths</a>, arXiv:2008.05669 [math.CO], 2020.

%F a(n) = Sum_{k=0..n-1} k*A100754(n,k).

%F G.f.: z^2*C/((1-z*C+z)^2*(1-2*z*C)), where C=(1-sqrt(1-4*z))/(2*z) is the Catalan function.

%F a(n) ~ 2^(2*n+1)/(9*sqrt(Pi*n)). - _Vaclav Kotesovec_, Mar 20 2014

%F a(n) = Sum_{k=1..n} (k*(-1)^(k+1)*binomial(2*n-k,n-k-1)). - _Vladimir Kruchinin_, Oct 22 2016

%F D-finite with recurrence 2*(n+1)*a(n) -9*n*a(n-1) -3*n*a(n-2) +5*(5*n-16)*a(n-3) +6*(2*n-5)*a(n-4)=0. - _R. J. Mathar_, Jul 22 2022

%e a(3)=3 because in the two hill-free Dyck paths of semilength 3, namely U(UD)(UD)D and UU(UD)DD, we have altogether 3 peaks (shown between parentheses).

%p C:=(1-sqrt(1-4*z))/2/z: G:=1/(1-z*C+z)^2*z^2*C/(1-2*z*C): Gser:=series(G,z=0,32): 0, seq(coeff(Gser,z^n),n=1..28);

%t CoefficientList[Series[1/(1-x*(1-Sqrt[1-4*x])/2/x+x)^2*x^2*(1-Sqrt[1-4*x])/2/x/(1-2*x*(1-Sqrt[1-4*x])/2/x), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Mar 20 2014 *)

%t a[n_] := If[n<=1, 0, Binomial[2n-1, n-2] Hypergeometric2F1[2, 2-n, 1-2n, -1]]; Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Oct 22 2016, after _Vladimir Kruchinin_ *)

%o (Maxima)

%o a(n):=sum(k*(-1)^(k+1)*binomial(2*n-k,n-k-1),k,1,n); /* _Vladimir Kruchinin_, Oct 22 2016 */

%o (PARI) my(x='x + O('x^50)); concat([0,0], Vec((2*x*(1-sqrt(1-4*x)))/(sqrt(1-4*x)*(1 + 2*x + sqrt(1-4*x))^2))) \\ _G. C. Greubel_, Feb 08 2017

%Y Cf. A000108, A100754.

%K nonn

%O 0,4

%A _Emeric Deutsch_, Dec 04 2005