%I A008549
%S A008549 0,1,6,29,130,562,2380,9949,41226,169766,695860,2842226,
%T A008549 11576916,47050564,190876696,773201629,3128164186,12642301534,
%U A008549 51046844836,205954642534,830382690556,3345997029244,13475470680616
%N A008549 Number of ways of choosing at most n-1 items from a set of size 2n+1.
%C A008549 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).
%C A008549 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
%C A008549 Convolution of A001791 and A000984. - Paul Barry (pbarry(AT)wit.ie), 
               Feb 16 2005
%C A008549 a(n) = total semilength of "longest Dyck subpath" starting at an upstep 
               U taken over all upsteps in all Dyck paths of semilength n. - David 
               Callan (callan(AT)stat.wisc.edu), Jul 25 2008
%C A008549 [1,6,29,130,562,2380,...] is convolution of A001700 with itself . [From 
               Philippe DELEHAM (kolotoko(AT)wanadoo.fr), May 19 2009]
%D A008549 R. Chapman, Moments of Dyck paths, Discrete Math., 204 (1999), 113-117.
%D A008549 E. Pergola, Two bijections for the area of Dyck paths, Discrete Math., 
               241 (2001), 435-447.
%D A008549 W.-J. Woan, Area of Catalan Paths, Discrete Math., 226 (2001), 439-444.
%H A008549 T. D. Noe, <a href="b008549.txt">Table of n, a(n) for n=0..200</a>
%H A008549 C. Banderier, <a href="http://algo.inria.fr/banderier/">Analytic combinatorics 
               of random walks and planar maps</a>, PhD Thesis, 2001.
%F A008549 a(n) = 4^n - C(2*n+1, n).
%F A008549 Also a(n) = Sum_{k=1..n} Catalan(k)*4^(n-k).
%F A008549 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) ]
%F A008549 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
%F A008549 G.f.: (2*x^2-1+sqrt(1-4*x^2))/(2*(1+2*x)*(2*x-1)*x^3)
%F A008549 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
%F A008549 Second binomial transform of 2^n-C(n, floor(n/2))=A045621(n). - Paul 
               Barry (pbarry(AT)wit.ie), Jan 13 2006
%e A008549 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.
%p A008549 f := n->4^n-binomial(2*n+1,n);
%o A008549 (PARI) {a(n)=if(n<0, 0, 4^n -binomial(2*n+1, n))} /* Michael Somos Oct 
               31 2006 */
%Y A008549 Cf. A057571.
%Y A008549 Sequence in context: A081278 A054146 A081674 this_sequence A026675 A026873 
               A081179
%Y A008549 Adjacent sequences: A008546 A008547 A008548 this_sequence A008550 A008551 
               A008552
%K A008549 nonn,easy,nice
%O A008549 0,3
%A A008549 N. J. A. Sloane (njas(AT)research.att.com).
%E A008549 Better description from Dan Velleman (djvelleman(AT)amherst.edu), Dec 
               01 2000