login
Area under Dyck paths.
3

%I #20 Nov 21 2013 13:11:35

%S 1,6,19,58,146,380,883,2138,4774,11092,24190,54724,117508,260920,

%T 554179,1213690,2557022,5541092,11601610,24930860,51942076,110861896,

%U 230053614,488253348,1009853116,2133122760,4399720348,9256078408

%N Area under Dyck paths.

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

%C 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.

%H T. D. Noe, <a href="/A057571/b057571.txt">Table of n, a(n) for n=1..400</a>

%H C. Banderier, <a href="http://algo.inria.fr/banderier/">Analytic combinatorics of random walks and planar maps</a>, PhD Thesis, 2001.

%F 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

%F 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

%F a(n) ~ 3*n*2^(n-1) * (1-4*sqrt(2)/(3*sqrt(Pi*n))). - _Vaclav Kotesovec_, Sep 11 2013

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

%K easy,nonn,nice

%O 1,2

%A _Cyril Banderier_, Oct 04 2000