|
| |
|
|
A005700
|
|
a(n) = C(n)*C(n+2) - C(n+1)^2 where C() are the Catalan numbers A000108.
(Formerly M2975)
|
|
24
|
|
|
|
1, 1, 3, 14, 84, 594, 4719, 40898, 379236, 3711916, 37975756, 403127256, 4415203280, 49671036900, 571947380775, 6721316278650, 80419959684900, 977737404590100, 12058761323277900, 150656212896017400, 1904342169333848400, 24328661192286773400, 313839729380499376860
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
The old name was: Number of closed walks of 2n unit steps north, east, south, or west starting and ending at the origin and confined to the first octant.
Image of Catalan numbers (A000108) under "little Hankel" transform that sends [c_0, c_1, ...] to [d_0, d_1, ...] where d_n = c_n^2 - c_{n+1}*c_{n-1}.
The Niederhausen reference counts various classes of first octant paths by number of contacts with the line y=x. - David Callan, Sep 18 2007
In Sloane and Plouffe (1995) this was incorrectly described as "Dyck paths".
Also matchings avoiding a certain pattern (see J. Bloom and S. Elizalde). - N. J. A. Sloane, Jan 02 2013
a(n) is also the number of nested pairs of Dyck paths of length n starting and ending at the origin;
a(n) is also the number of 3-noncrossing perfect matchings on 2n points;
a(n) is also the number of 2-triangulations on n-gon;
a(n) is also the dimension of the invariant subspace of 2n-th tensor power of the spin representation of Spin(5);
a(n) is also the dimension of the invariant subspace of 2n-th tensor power of the defining representation of Sp(4). (End)
a(-1) = -3/2, a(-2) = -1/4 makes some formulas true for all n in Z. - Michael Somos, Oct 02 2014
a(n) is the number of uniquely sorted permutations of length 2n+1 that avoid the pattern 312. - Colin Defant, Jun 08 2019
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: 3F2( [ 1, 1/2, 3/2 ]; [ 3, 4 ]; 16 x ).
a(n) = 6*(2*n)!*(2*n+2)!/(n!*(n+1)!*(n+2)!*(n+3)!) (Mihailovs).
a(n) = Det[Table[binomial[i+1, j-i+2], {i, 1, n}, {j, 1, n}]]. - David Callan, Jul 20 2005
G.f.: (1 + 6*x - hypergeom([-1/2,-3/2],[2],16*x))/(4*x^2). - Mark van Hoeij, Nov 02 2009
a(n) = 12 * 4^n * (2*n-1)!! * (2*n+1)!! / ((n+2)! * (n+3)!).
D-finite with recurrence 0 = a(n) * 4*(2*n+1)*(2*n+3) - a(n+1) * (n+3)*(n+4) for all n in Z.
0 = a(n)*(+65536*a(n+2) - 72192*a(n+3) + 10296*a(n+4)) + a(n+1)*(-1536*a(n+2) - 1632*a(n+3) - 282*a(n+4)) + a(n+2)*(+40*a(n+2) - 6*a(n+3) + a(n+4)) for all n in Z.
0 = a(n)^2*a(n+2)*(+1792*a(n+1) - 882*a(n+2)) + a(n)*a(n+1)^2*(+768*a(n+1) + 580*a(n+2)) + 7*a(n)*a(n+1)*a(n+2)^2 +a(n+1)^3*(-18*a(n+1) + 3*a(n+2)) for all n in Z. (End)
a(n) = (12*(2*n - 1)/((n + 1)(n + 2)(n + 3))) * Catalan(n-1)*Catalan(n+1) for n >= 1.
a(n) = Product_{1 <= i <= j <= n-1} (i + j + 4)/(i + j).
a(n) = (1/2^(n-1)) * Product_{1 <= i <= j <= n-1} (i + j + 4)/(i + j - 1) for n >= 1. (End)
Sum_{n>=0} a(n)/16^n = 88 - 4096/(15*Pi). - Amiram Eldar, May 06 2023
|
|
|
EXAMPLE
|
Example: a(2)=3 counts EWEW, EEWW, ENSW.
G.f. = 1 + x + 3*x^2 + 14*x^3 + 84*x^4 + 594*x^5 + 4719*x^6 + 40898*x^7 + ...
|
|
|
MATHEMATICA
|
CoefficientList[ Series[ HypergeometricPFQ[ {1, 1/2, 3/2}, {3, 4}, 16 x], {x, 0, 19}], x]
a[ n_] := If[ n < 1, Boole[n == 0], Det[ Table[ Binomial[i + 1, j - i + 2], {i, n}, {j, n}]]]; (* Michael Somos, Feb 25 2014 *) (* slight modification of David Callan formula *)
a[ n_] := 12 * 4^n * (2*n-1)!! * (2*n+1)!! / ((n+2)! * (n+3)!); (* Michael Somos, Oct 02 2014 *)
|
|
|
PROG
|
(Magma) [6*Factorial(2*n)*Factorial(2*n+2)/(Factorial(n)*Factorial(n+1)* Factorial(n+2)*Factorial(n+3)): n in [0..25]]; // Vincenzo Librandi, Aug 04 2011
(LiE) p_tensor(2*n, [0, 1], B2)|[0, 0]
(LiE) p_tensor(2*n, [1, 0], C2)|[0, 0]
(PARI) {a(n) = if( n<0, if( n<-2, 0, [-3/2, -1/4][-n]), 6 * (2*n)! * (2*n+2)! / (n! * (n+1)! * (n+2)! * (n+3)!))}; /* Michael Somos, Oct 02 2014 */
|
|
|
CROSSREFS
|
A column of the triangle in A179898. A diagonal of the triangle in A185249.
|
|
|
KEYWORD
|
nonn,walk,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
