A057571 Area under Dyck paths.

1, 6, 19, 58, 146, 380, 883, 2138, 4774, 11092, 24190, 54724, 117508, 260920, 554179, 1213690, 2557022, 5541092, 11601610, 24930860, 51942076, 110861896, 230053614, 488253348, 1009853116, 2133122760, 4399720348, 9256078408

Offset: 1

Author

Cyril Banderier, Oct 04 2000

Keywords

• easy
• nonn
• nice

Comments

a(n) is 2*the sum of the areas under all Dyck paths of length n.

The Dyck paths considered in this sequence always have height >= 0 but do not need to finish at height = 0. n is the total number of steps.

Links

• T. D. Noe, Table of n, a(n) for n=1..400
• C. Banderier, Analytic combinatorics of random walks and planar maps, PhD Thesis, 2001.

Programs

Mathematica

f[x_] := 2*(8*x^2+4*x-1-Sqrt[1-4*x^2]*(4*x^2+4*x-1)) / (4*(1-2*x)^2*(1+2*x)*x^2); CoefficientList[ Series[ f[x], {x, 0, 27}], x] (* Jean-François Alcover, Dec 21 2011, after area sum g.f. multiplied by 2 *)

Formula

G.f.: 2*x*(8*x^2+4*x-1-sqrt(1-4*x^2)*(4*x^2+4*x-1))/(4*(1-2*x)^2*(1+2*x)*x^2). - corrected by Vaclav Kotesovec, Sep 11 2013

Recurrence: (n+1)*(4*n^3 - 28*n^2 + 55*n - 27)*a(n) = 2*(8*n^3 - 48*n^2 + 52*n + 27)*a(n-1) + 4*(2*n - 1)*(4*n^3 - 24*n^2 + 29*n + 18)*a(n-2) - 16*(2*n - 3)*(2*n^2 - 8*n - 1)*a(n-3) - 16*(n-3)*(4*n^3 - 16*n^2 + 11*n + 4)*a(n-4). - Vaclav Kotesovec, Sep 11 2013

a(n) ~ 3*n*2^(n-1) * (1-4*sqrt(2)/(3*sqrt(Pi*n))). - Vaclav Kotesovec, Sep 11 2013