A114587 Number of peaks at odd levels in all hill-free Dyck paths of semilength n+3 (a hill in a Dyck path is a peak at level 1).
1, 4, 17, 68, 269, 1056, 4132, 16144, 63046, 246228, 962019, 3760700, 14710589, 57581696, 225546488, 884059808, 3467476430, 13608852968, 53443415522, 210000136136, 825630208466, 3247733377664, 12781815016232, 50328168273408
Offset: 0
Keywords
Examples
a(1)=4 because in the 6 (=A000957(5)) hill-free Dyck paths of semilength 4, namely UUUUDDDD, UU(UD)(UD)DD, UUDU(UD)DD, UUDUDUDD, UU(UD)DUDD and UUDDUUDD (U=(1,1), D=(1,-1)) we have altogether 4 peaks at odd level (shown between parentheses).
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..300
Programs
-
Maple
G:=(1-2*z-3*z^2-2*z^3-(1-z^2)*sqrt(1-4*z))/2/sqrt(1-4*z)/z^4/(2+z)^2: Gser:=series(G,z=0,32): 1,seq(coeff(Gser,z^n),n=1..26);
-
Mathematica
CoefficientList[Series[(1-2*x-3*x^2-2*x^3-(1-x^2)*Sqrt[1-4*x])/(2*x^4*(2+x)^2*Sqrt[1-4*x]), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 19 2012 *)
Formula
G.f.: (1 - 2*x - 3*x^2 - 2*x^3 - (1 - x^2)*sqrt(1 - 4*x))/(2*x^4*(2 + x)^2 * sqrt(1 - 4*x)).
a(n) = Sum_{k=0..n+1} k*A114586(n+3,k).
Recurrence: 8*n*(n+4)*a(n) = 2*(15*n^2 + 47*n + 18)*a(n-1) + (9*n^2 + 70*n + 80)*a(n-2) - 2*(n+1)*(2*n+1)*a(n-3). - Vaclav Kotesovec, Oct 19 2012
a(n) ~ 2^(2*n+6)/(9*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 19 2012