A005566 Number of walks of length n on square lattice, starting at origin, staying in first quadrant. (Formerly M1627)

1, 2, 6, 18, 60, 200, 700, 2450, 8820, 31752, 116424, 426888, 1585584, 5889312, 22084920, 82818450, 312869700, 1181952200, 4491418360, 17067389768, 65166397296, 248817153312, 953799087696, 3656229836168, 14062422446800, 54086240180000, 208618354980000

Offset

0,2

Comments

a(n) is the number of involutions of length 2n which are invariant under the reverse-complement map and have no decreasing subsequences of length 5. - Eric S. Egge, Oct 21 2008

References

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

Links

Table of n, a(n) for n=0..26.

Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Séminaire de Combinatoire Ph. Flajolet, March 28 2013.

Alin Bostan, Calcul Formel pour la Combinatoire des Marches [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, Dec 15 2017.

Alin Bostan, Frédéric Chyzak, Mark van Hoeij, Manuel Kauers, and Lucien Pech, Hypergeometric expressions for generating functions of walks with small steps in the quarter plane. Eur. J. Comb. 61 (2017), 242-275.

Nachum Dershowitz, Touchard's Drunkard, J. Int. Seq. 20 (2017), Article 17.1.5.

Richard K. Guy, Letter to N. J. A. Sloane, May 1990.

Richard K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article 00.1.6.

Formula

a(2*n) = A000894(n), a(2*n+1) = 2*A060150(n+1).

a(n) = binomial(n, floor(n/2))*binomial(n+1, floor((n+1)/2)).

E.g.f.: (BesselI(0, 2*x)+BesselI(1, 2*x))^2. - Vladeta Jovovic, Apr 28 2003

EXPCONV of A001405 with itself, i.e., a(n) = Sum_{k=0..n} binomial(n,k)*A001405(k)*A001405(n-k). - Max Alekseyev, May 18 2006

G.f.: (16*x^2-1)*hypergeom([3/2, 3/2],[2],16*x^2) + (1/(2x)+2)*hypergeom([1/2, 1/2],[1],16*x^2) - 1/(2x). - Mark van Hoeij, Oct 13 2009

G.f.: (hypergeom([1/2,1/2],[1],16*x^2) - 1)/(2*x) + hypergeom([1/2,3/2],[2],16*x^2). - Mark van Hoeij, Aug 14 2014

a(n) = A241530(n)*2*floor(n/2)/(floor(n/2)+1). - Peter Luschny, Apr 25 2014

D-finite with recurrence (n+2)*(n+1)*a(n) + 4*(-2*n-1)*a(n-1) - 16*n*(n-1)*a(n-2) = 0. - R. J. Mathar, Mar 07 2015

0 = a(n)*(16*a(n+2) - 6*a(n+3)) + a(n+1)*(-2*a(n+2) + a(n+3)) if n >= 0. - Michael Somos, Oct 17 2019

a(n) = binomial(floor(n + 1/2), floor(n/2)) * binomial(ceiling(n + 1/2), ceiling(n/2)). - Peter Luschny, Dec 14 2024

a(n) ~ 2^(2*n+2)/(n*Pi). - Amiram Eldar, Dec 28 2025

Example

G.f. = 1 + 2*x + 6*x^2 + 18*x^3 + 60*x^4 + 200*x^5 + 700*x^6 + 2450*x^7 + ... - Michael Somos, Oct 17 2019

Mathematica

a[n_] := Binomial[n, Floor[n/2]] Binomial[n + 1, Floor[(n + 1)/2]]; Array[a, 25, 0] (* Robert G. Wilson v *)

Prog

(Magma) [Binomial(n, Floor(n/2))*Binomial(n+1, Floor((n+1)/2)): n in [0..30]]; // Vincenzo Librandi, Feb 18 2015

Crossrefs

Cf. A000894, A001405, A001700, A060150, A060897, A060898, A060899, A060900, A241530.

Sequence in context: A358251 A002527 A389324 * A005631 A118677 A150043

Adjacent sequences: A005563 A005564 A005565 * A005567 A005568 A005569

Keyword

nonn,walk

Author

N. J. A. Sloane

Extensions

Additional comments from David W. Wilson, May 05 2001

a(25)-a(26) from Vincenzo Librandi, Feb 18 2015

Status

approved