A114515 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).
0, 0, 1, 3, 12, 45, 171, 651, 2488, 9540, 36690, 141482, 546864, 2118207, 8219967, 31952115, 124389552, 484908408, 1892657934, 7395597354, 28928182440, 113260606074, 443827115886, 1740592240638, 6831289801872, 26829201570600
Offset: 0
Keywords
Examples
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).
Links
- G. C. Greubel, Table of n, a(n) for n = 0..1000
- Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020.
Programs
-
Maple
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);
-
Mathematica
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 *) 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 *) -
Maxima
a(n):=sum(k*(-1)^(k+1)*binomial(2*n-k,n-k-1),k,1,n); /* Vladimir Kruchinin, Oct 22 2016 */
-
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
Formula
a(n) = Sum_{k=0..n-1} k*A100754(n,k).
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.
a(n) ~ 2^(2*n+1)/(9*sqrt(Pi*n)). - Vaclav Kotesovec, Mar 20 2014
a(n) = Sum_{k=1..n} (k*(-1)^(k+1)*binomial(2*n-k,n-k-1)). - Vladimir Kruchinin, Oct 22 2016
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