|
| |
|
|
A052704
|
|
Apart from the leading term, Catalan(n-1)*4^(n-1).
|
|
3
| |
|
|
0, 1, 4, 32, 320, 3584, 43008, 540672, 7028736, 93716480, 1274544128, 17611882496, 246566354944, 3489862254592, 49855175065600, 717914520944640, 10409760553697280, 151860036312760320
(list; graph; refs; listen; history; internal format)
|
|
|
|
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 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)
|
|
|
REFERENCES
| 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.
|
|
|
LINKS
| Vincenzo Librandi, Table of n, a(n) for n = 0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 658
M. Bousquet-Melou and G. Schaeffer, Walks on the Slit Plane
|
|
|
FORMULA
| a(n) = 16^n*GAMMA(n+1/2)/GAMMA(n+2)/Pi^(1/2)
G.f.: (1 - sqrt(1 - 16*x)) / 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, Mar 16 2004
a(n+1) = (1/(8*pi))*integrate(x=0..16, x^n*sqrt(x*(16-x))/x ); a(n+1)=(1/(8*pi))*integrate(x=-4..4, x^(2*n)*sqrt(4-x)*sqrt(4+x) ); - 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
|
|
|
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
|
|
|
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
| See A000108 for Catalan numbers.
Sequence in context: A197715 A047734 A060174 * A151403 A090004 A061631
Adjacent sequences: A052701 A052702 A052703 * A052705 A052706 A052707
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| encyclopedia(AT)pommard.inria.fr, Jan 25 2000
|
| |
|
|
