0,3

Area under Dyck excursions (paths ending in 0): a(n) is the sum of the areas under all Dyck excursions of length 2*n (nonnegative walks beginning and ending in 0 with jumps -1,+1).

Number of inversions in all 321-avoiding permutations of [n+1]. Example: a(2)=6 because the 321-avoiding permutations of [3], namely 123,132,312,213,231, have 0, 1, 2, 1, 2 inversions, respectively. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 28 2003

Convolution of A001791 and A000984. - Paul Barry (pbarry(AT)wit.ie), Feb 16 2005

R. Chapman, Moments of Dyck paths, Discrete Math., 204 (1999), 113-117.

E. Pergola, Two bijections for the area of Dyck paths, Discrete Math., 241 (2001), 435-447.

W.-J. Woan, Area of Catalan Paths, Discrete Math., 226 (2001), 439-444.

T. D. Noe, Table of n, a(n) for n=0..200

C. Banderier, Analytic combinatorics of random walks and planar maps, PhD Thesis, 2001.

a(n) = 4^n - C(2*n+1, n).

Also a(n) = Sum_{k=1..n} Catalan(k)*4^(n-k).

Convolution of Catalan numbers and powers of 4: a(n+1)=sum(C(k+1)*4^(n-k), k=0..n); G.f.: x*(c(x)^2)/(1-4*x), c(x) = g.f. of Catalan numbers [ Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de) ]

Note Sum[Binomial[2n+1, k], {k, 0, 2n + 1}] = 2^(2n+1). Therefore by the symmetry of Pascal's triangle, Sum[Binomial[2n+1, k], {k, 0, n}] = 2^(2n) = 4^n. This explains why the following two expressions for a(n) are equal: Sum[Binomial[2n+1, k], {k, 0, n-1}] = 4^n - Binomial [2n+1, n] - Dan Velleman

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

a(n)=sum{k=0..n, C(2k, k)C(2(n-k), n-k-1)}. - Paul Barry (pbarry(AT)wit.ie), Feb 16 2005

Second binomial transform of 2^n-C(n, floor(n/2))=A045621(n). - Paul Barry (pbarry(AT)wit.ie), Jan 13 2006

a(2) = 6 because there are 6 ways to choose at most 1 item from a set of size 5: You can choose the empty set, or you can choose any of the five one-element sets.

f := n->4^n-binomial(2*n+1, n);

(PARI) {a(n)=if(n<0, 0, 4^n -binomial(2*n+1, n))} /* Michael Somos Oct 31 2006 */

Cf. A057571.

Sequence in context: A081278 A054146 A081674 this_sequence A026675 A026873 A081179

Adjacent sequences: A008546 A008547 A008548 this_sequence A008550 A008551 A008552

nonn,easy,nice

njas

Better description from Dan Velleman (djvelleman(AT)amherst.edu), Dec 01 2000