OFFSET
0,3
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)
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.
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)
EXAMPLE
x + 4*x^2 + 32*x^3 + 320*x^4 + 3584*x^5 + 43008*x^6 + 540672*x^7 + ...
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 *)
PROG
(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 */
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
STATUS
approved