0,3

Series reversion of g.f. A(x) is x-4x^2. Or x=A(x)-4A(x)^2.

Comments from David Callan (callan(AT)stat.wisc.edu), Sep 20 2007: (Start) 4^n Catalan[n] counts NESW walks of 2n steps from the origin that stay weakly below the line y=x and end on it. A NESW walk consists of unit steps North, East, South, or West (may cross itself or backtrack). For example, n=1: SN, SW, EN, EW.

Bijective proof: given such a NESW walk, construct a pair (P_1, P_2) of lattice paths of upsteps U=(1,1) and downsteps D=(1,-1) as follows. To get P_1, replace each E and S by U and each W and N by D. To get P_2, replace each N and E by U and each S and W by D. For example, SENSNW -> (UUDUDD, DUUDUD).

This mapping is 1-to-1 and its range is the Cartesian product of the set of Dyck n-paths (counted by the Catalan number C_n) and the set of arbitrary paths of length 2n (counted by 4^n). The number of the above NESW walks with j South and k West steps is binom[n,j]binom[n,k]CatalanNumber[n].

The Bousquet-Melou and Schaeffer references show that 4^n Catalan[n] counts NESW walks of 2n+1 steps from the origin that never return to the nonpositive x-axis (y=0, x<=0) and end at (0,1). n=1: NNS, NEW, NWE, ENW. (End)

M. Bousquet-Melou, Walks on the slit plane: other approaches, Advances in Applied Math. 27 (2001), 243-288.

M. Bousquet-Melou and G. Schaeffer, Walks on the slit plane, Probab. Theory Related Fields 124 (2002), 305-344.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 658

M. Bousquet-Melou and G. Schaeffer, Walks on the Slit Plane.

16^n*GAMMA(n+1/2)/GAMMA(n+2)/Pi^(1/2)

G.f.: (1-sqrt(1-16x))/8. a(n)=8(2-3/n)a(n-1), n>1.

a(0)=0, a(1)=1 a(n)=4*sum(i=1, n-1, a(i)*a(n-i)) - Benoit Cloitre (benoit7848c(AT)orange.fr), Mar 16 2004

a(n+1)=(1/(8*pi))*int(x^n*sqrt(x(16-x))/x,x,0,16); a(n+1)=(1/(8*pi))*int(x^(2n)*sqrt(4-x)*sqrt(4+x),x,-4,4); - Paul Barry (pbarry(AT)wit.ie), Oct 01 2007

spec := [S, {B=Prod(C, C), S=Union(B, Z), C=Union(S, B, Z)}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);

InverseSeries[Series[y-4*y^2, {y, 0, 24}], x] (* then A(x)=y(x) *) - Len Smiley, Apr 07 2000

(PARI) a(n)=if(n<1, 0, n--; 4^n*(2*n)!/n!/(n+1)!)

See A000108 for Catalan numbers.

Sequence in context: A000766 A047734 A060174 this_sequence A151403 A090004 A061631

Adjacent sequences: A052701 A052702 A052703 this_sequence A052705 A052706 A052707

easy,nonn

encyclopedia(AT)pommard.inria.fr, Jan 25 2000