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,2

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..300

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

Example

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).

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 *)

Crossrefs

Cf. A114586, A114590, A114515.

Sequence in context: A239845 A081113 A368429 * A268431 A033114 A096881

Adjacent sequences: A114584 A114585 A114586 * A114588 A114589 A114590

Keyword

nonn

Author

Emeric Deutsch, Dec 11 2005

Status

approved