A052704 Apart from the leading term, a(n) = Catalan(n-1)*4^(n-1).

0, 1, 4, 32, 320, 3584, 43008, 540672, 7028736, 93716480, 1274544128, 17611882496, 246566354944, 3489862254592, 49855175065600, 717914520944640, 10409760553697280, 151860036312760320, 2227280532587151360, 32823081532863283200, 485781606686376591360, 7217326727911880785920

Offset: 0

Author

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

Keywords

• easy
• nonn

Comments

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

From David Callan, 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 binomial(n,j)*binomial(n,k)CatalanNumber(n).

The Bousquet-Mélou 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)

Examples

			x + 4*x^2 + 32*x^3 + 320*x^4 + 3584*x^5 + 43008*x^6 + 540672*x^7 + ...
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• M. Bousquet-Mélou, Walks on the slit plane: other approaches, Advances in Applied Math. 27 (2001), 243-288.
• M. Bousquet-Mélou and G. Schaeffer, Walks on the Slit Plane, arXiv:math/0012230 [math.CO], 2000.
• M. Bousquet-Mélou and G. Schaeffer, Walks on the slit plane, Probab. Theory Related Fields 124 (2002), 305-344.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 658.

Crossrefs

See A000108 for Catalan numbers.

Programs

Maple

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);

Mathematica

InverseSeries[Series[y-4*y^2, {y, 0, 24}], x] (* then A(x)=y(x) *) (* Len Smiley, Apr 07 2000 *)
Join[{0},Table[CatalanNumber[n-1]4^(n-1),{n,20}]] (* Harvey P. Dale, Dec 01 2013 *)

PARI

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

PARI

{a(n) = local(A); if( n<1, 0, A = vector(n); A[1] = 1; for( k=2, n, A[k] = 4 * sum( j=1, k-1, A[j] * A[k-j])); A[n])} /* Michael Somos, Jul 23 2011 */

Formula

a(n) = 16^n*Gamma(n+1/2)/Gamma(n+2)/Pi^(1/2).

G.f.: (1 - sqrt(1 - 16*x)) / 8.

D-finite with recurrence 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, Mar 16 2004

a(n+1) = (1/(8*Pi))*Integral_{x=0..16} x^n*sqrt(x*(16-x))/x dx; a(n+1) = (1/(8*Pi))*Integral_{x=-4..4} x^(2*n)*sqrt(4-x)*sqrt(4+x)*dt. - Paul Barry, Oct 01 2007

a(n) = upper left term of M^(n-1), where M is an infinite matrix as follows:

4, 4, 0, 0, 0, 0, ...

4, 4, 4, 0, 0, 0, ...

4, 4, 4, 4, 0, 0, ...

4, 4, 4, 4, 4, 0, ...

4, 4, 4, 4, 4, 4, ...

...

- Gary W. Adamson, Jul 13 2011

a(n) = 4 * Sum_{k=1..n-1} a(k) * a(n-k) if n>1. - Michael Somos, Jul 23 2011

a(n) ~ 16^(n-1)/(sqrt(Pi)*n^(3/2)). - Ilya Gutkovskiy, Dec 04 2016

From Amiram Eldar, Aug 25 2022: (Start)

Sum_{n>=1} 1/a(n) = 88/75 + 128*arctan(1/sqrt(15)) / (75*sqrt(15)).

Sum_{n>=1} (-1)^(n+1)/a(n) = 248/289 - 384*arctanh(1/sqrt(17)) / (289*sqrt(17)). (End)