|
| |
|
|
A052704
|
|
Apart from the leading term, a(n) = Catalan(n-1)*4^(n-1).
|
|
4
|
|
|
|
0, 1, 4, 32, 320, 3584, 43008, 540672, 7028736, 93716480, 1274544128, 17611882496, 246566354944, 3489862254592, 49855175065600, 717914520944640, 10409760553697280, 151860036312760320, 2227280532587151360, 32823081532863283200, 485781606686376591360, 7217326727911880785920
(list;
graph;
refs;
listen;
history;
text;
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.
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
|
|
|
|
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, ...
...
a(n) = 4 * Sum_{k=1..n-1} a(k) * a(n-k) if n>1. - Michael Somos, Jul 23 2011
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
|
| |
|
|
