A052704 - OEIS

%I #64 Sep 22 2023 07:45:38

%S 0,1,4,32,320,3584,43008,540672,7028736,93716480,1274544128,

%T 17611882496,246566354944,3489862254592,49855175065600,

%U 717914520944640,10409760553697280,151860036312760320,2227280532587151360,32823081532863283200,485781606686376591360,7217326727911880785920

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

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

%C From _David Callan_, Sep 20 2007: (Start)

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

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

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

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

%H Vincenzo Librandi, <a href="/A052704/b052704.txt">Table of n, a(n) for n = 0..200</a>

%H M. Bousquet-Mélou, <a href="http://dx.doi.org/10.1006/aama.2001.0734">Walks on the slit plane: other approaches</a>, Advances in Applied Math. 27 (2001), 243-288.

%H M. Bousquet-Mélou and G. Schaeffer, <a href="http://arxiv.org/abs/math/0012230">Walks on the Slit Plane</a>, arXiv:math/0012230 [math.CO], 2000.

%H M. Bousquet-Mélou and G. Schaeffer, <a href="https://hal.inria.fr/inria-00100936">Walks on the slit plane</a>, Probab. Theory Related Fields 124 (2002), 305-344.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=658">Encyclopedia of Combinatorial Structures 658</a>.

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

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

%F D-finite with recurrence a(n) = 8*(2-3/n)*a(n-1), n>1.

%F a(0)=0, a(1)=1, a(n) = 4*Sum_{i=1..n-1} a(i)*a(n-i). - _Benoit Cloitre_, Mar 16 2004

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

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

%F 4, 4, 0, 0, 0, 0, ...

%F 4, 4, 4, 0, 0, 0, ...

%F 4, 4, 4, 4, 0, 0, ...

%F 4, 4, 4, 4, 4, 0, ...

%F 4, 4, 4, 4, 4, 4, ...

%F ...

%F - _Gary W. Adamson_, Jul 13 2011

%F a(n) = 4 * Sum_{k=1..n-1} a(k) * a(n-k) if n>1. - _Michael Somos_, Jul 23 2011

%F a(n) ~ 16^(n-1)/(sqrt(Pi)*n^(3/2)). - _Ilya Gutkovskiy_, Dec 04 2016

%F From _Amiram Eldar_, Aug 25 2022: (Start)

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

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

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

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

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

%t Join[{0},Table[CatalanNumber[n-1]4^(n-1),{n,20}]] (* _Harvey P. Dale_, Dec 01 2013 *)

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

%o (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 */

%Y See A000108 for Catalan numbers.

%K easy,nonn

%O 0,3

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