A059027 Number of Dyck paths of semilength n with no peak at height 4.

1, 1, 2, 5, 13, 35, 97, 276, 805, 2404, 7343, 22916, 72980, 236857, 782275, 2625265, 8938718, 30834165, 107608097, 379454447, 1350434278, 4845475311, 17512579630, 63703732426, 233063976059, 857067469749, 3166309373615, 11745982220846

Offset

0,3

References

Peart and Woan, in press, G_4(x).

Links

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

P. Peart and W.-J. Woan, Dyck Paths With No Peaks at Height k, J. Integer Sequences, 4 (2001), #01.1.3.

Formula

G.f.: (2-3*x+x*(1-4*x)^(1/2))/(2-5*x+x*(1-4*x)^(1/2)).

a(n) = sum(k=1..n-2, sum(j=max(2*k-n+1,0)..k-1, (binomial(k,j)*((k-j)*binomial(2*n-3*k+j-3,n-1-2*k+j)))/(n-k-1)*2^j))+2^(n-1). - Vladimir Kruchinin, Oct 03 2013

a(n) ~ 4^n/(9*sqrt(Pi)*n^(3/2)) * (1+197/(24*n)). - Vaclav Kotesovec, Mar 20 2014

Example

1 + x + 2*x^2 + 5*x^3 + 13*x^4 + 35*x^5 + 97*x^6 + ...

Mathematica

CoefficientList[Series[(2 - 3 x + x (1 - 4 x)^(1/2))/(2 - 5 x + x (1 - 4 x)^(1/2)), {x, 0, 40}], x] (* Vincenzo Librandi, Oct 05 2013 *)

Prog

a(n):=if n=0 then 1 else sum(sum((binomial(k, j)*((k-j)*binomial(2*n-3*k+j-3, n-1-2*k+j)))/(n-k-1)*2^j, j, max(2*k-n+1, 0), k-1), k, 1, n-2)+2^(n-1); [Vladimir Kruchinin, Oct 03 2013]
(PARI) x='x+O('x^66); Vec((2-3*x+x*(1-4*x)^(1/2))/(2-5*x+x*(1-4*x)^(1/2))) \\ Joerg Arndt, Oct 03 2013

Crossrefs

G_1, G_2, G_3, G_4 give A000957, A000108, A059019, A059027 resp.

Sequence in context: A085281 A082582 A086581 * A025198 A221205 A037247

Adjacent sequences: A059024 A059025 A059026 * A059028 A059029 A059030

Keyword

nonn

Author

N. J. A. Sloane, Feb 12 2001

Status

approved