login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005700 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.
(Formerly M2975)
12
1, 1, 3, 14, 84, 594, 4719, 40898, 379236, 3711916, 37975756, 403127256, 4415203280, 49671036900, 571947380775, 6721316278650, 80419959684900, 977737404590100, 12058761323277900, 150656212896017400 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

From Bruce Westbury, Aug 22 2013: (Start)

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

REFERENCES

S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 183).

D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableau de Young, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, Springer, 1986.

Nicholas M. Katz, A NOTE ON RANDOM MATRIX INTEGRALS, MOMENT IDENTITIES, AND CATALAN NUMBERS, 2015; https://web.math.princeton.edu/~nmk/catalan11.pdf

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Jonathan Bloom and Sergi Elizalde, Pattern avoidance in matchings and partitions, arXiv preprint arXiv:1211.3442, 2012. See Table 1.

N. Bonichon, A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths, Discr. Math., 298 (2005), 104-114.

W. Y. C. Cheng, E. Y. P. Deng, R. R. X. Du, R. P. Stanley and C. H. Yan, Crossings and nestings of matchings and partitions, arxiv:math.CO/0501230

C. P. Davis-Stober, A bijection between a set of lexicographic semiorders and pairs of non-crossing Dyck paths, Journal of Mathematical Psychology, 54, 471-474.

Kiran S. Kedlaya and Andrew V. Sutherland, Hyperelliptic curves, L-polynomials and random matrices, arXiv:0803.4462

Alec Mihailovs, Enumeration of walks on lattices, (1998).

Heinrich Niederhausen, A Note on the Enumeration of Diffusion Walks in the First Octant by Their Number of Contacts with the Diagonal, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.3.

Index entries for sequences related to Young tableaux.

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

a(n) = b(n)b(n+1)/6 where b(n) is the superballot number A007054. - David Callan, Feb 01 2007

a(n) = A000108(n)*A000108(n+2)-A000108(n+1)^2. - Philippe Deléham, Apr 11 2007

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)!). - Michael Somos, Oct 02 2014

0 = a(n) * 4*(2*n+1)*(2*n+3) - a(n+1) * (n+3)*(n+4) for all n in Z. - Michael Somos, Oct 02 2014

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. - Michael Somos, Oct 02 2014

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. - Michael Somos, Oct 02 2014

a(n) ~ 3 * 2^(4*n+3) / (Pi * n^5). - Vaclav Kotesovec, Feb 10 2015

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

(PARI) a(n)=6*binomial(2*n+2, n)*(2*n)!/(n+1)!/(n+3)! \\ Charles R Greathouse IV, 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.

Row sums of A193691, A193692. - Alois P. Heinz, Aug 03 2011

See A138349 for another version.

Cf. A000108, A248152.

Sequence in context: A256337 A256330 A190761 * A220911 A088717 A111538

Adjacent sequences:  A005697 A005698 A005699 * A005701 A005702 A005703

KEYWORD

nonn,walk,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from James A. Sellers, Dec 24 1999

Corrected by Vladeta Jovovic, May 23 2004

Better definition from David Callan, Sep 18 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 25 15:14 EDT 2017. Contains 284082 sequences.