A005558 a(n) is the number of n-step walks on square lattice such that 0 <= y <= x at each step.

1, 1, 3, 6, 20, 50, 175, 490, 1764, 5292, 19404, 60984, 226512, 736164, 2760615, 9202050, 34763300, 118195220, 449141836, 1551580888, 5924217936, 20734762776, 79483257308, 281248448936, 1081724803600, 3863302870000, 14901311070000, 53644719852000

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• walk

Comments

Number of n-step walks that start at the origin, constrained to stay in the first octant (0 <= y <= x). (Conjectured) - Benjamin Phillabaum, Mar 11 2011, corrected by Robert Israel, Oct 07 2015

For n >= 1, a(n-1) is the number of Dyck Paths with semilength n having floor((n+2)/2) U's in odd numbered positions. Example: (U is in odd numbered position and u is in even numbered position) Dyck path with n=5, floor ((5+2)/2)=3: UuddUuUddd. - Roger Ford, May 27 2017

The ratio of the number of n-step walks on the octant with an equal number of North steps and South steps to the total number of n-step walks on the octant is A005817(n)/a(n). For the reduced ratio, if n is divisible by 4 or n-1 is divisible by 4 the ratio is 1:floor(n/4)+1 and for all other values of n the ratio is 2:floor(n/2)+2. Example n = 4: A005817(4) = 10; EEEE, EEEW, EEWE, EWEE, EWEW, EEWW, ENSE, ENES, ENSW, EENS; a(4) = 20; 10:20 reduces to 1:2. - Roger Ford, Nov 04 2019

References

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Slides for Séminaire de Combinatoire Ph. Flajolet, Mar 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, December 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, 242-275 (2017)
• Sergi Elizalde, The degree of symmetry of lattice paths, arXiv:2002.12874 [math.CO], 2020.
• R. K. Guy, Letter to N. J. A. Sloane, May 1990
• R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6. See Column 1 of Figure 5.
• 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.

Crossrefs

See A138350 for a signed version.

Bisections are A000891 and A000888/2.

Cf. A005559, A005560, A005561, A005562, A093768.

Cf. A000108, A005817. Column y=0 of A052174.

Programs

Magma

[Binomial(n+1, Ceiling(n/2))*Binomial(n, Floor(n/2)) - Binomial(n+1, Ceiling((n-1)/2))*Binomial(n, Floor((n-1)/2)): n in [0..30]]; // Vincenzo Librandi, Sep 30 2015

Maple

A:= proc(n,x,y) option remember;
    local j, xpyp, xp,yp, res;
    xpyp:= [[x-1,y],[x+1,y],[x,y-1],[x,y+1]];
    res:= 0;
    for j from 1 to 4 do
      xp:= xpyp[j,1];
      yp:= xpyp[j,2];
      if xp < 0 or xp > yp or xp + yp > n then next fi;
      res:= res + procname(n-1,xp,yp)
    od;
return res
end proc:
A(0,0,0) := 1:
seq(add(add(A(n,x,y), y = x .. n - x), x = 0 .. floor(n/2)), n = 0 .. 50); # Robert Israel, Oct 07 2015

Mathematica

a[n_] := 1/2*Binomial[2*Floor[n/2]+1, Floor[n/2]+1]*CatalanNumber[1/2*(n+Mod[n, 2])]*(Mod[n, 2]+2); Table[a[n]//Abs, {n, 0, 27}] (* Jean-François Alcover, Mar 13 2014 *)

PARI

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

Python

from sympy import ceiling as c, binomial
def a(n):
    return binomial(n + 1, c(n/2))*binomial(n, n//2) - binomial(n + 1, c((n - 1)/2))*binomial(n, (n - 1)//2)
print([a(n) for n in range(51)]) # Indranil Ghosh, Jul 02 2017

Formula

a(n) = C(n+1, ceiling(n/2))*C(n, floor(n/2)) - C(n+1, ceiling((n-1)/2))*C(n, floor((n-1)/2)). - Paul D. Hanna, Apr 16 2004

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

E.g.f (conjectured): BesselI(1,2*x)*(BesselI(0,2*x)+BesselI(1,2*x))/x. - Benjamin Phillabaum, Feb 25 2011

Conjecture: (2*n+1)*(n+3)*(n+2)*a(n) - 4*(2*n^2+4*n+3)*a(n-1) - 16*n*(2*n+3)*(n-1)*a(n-2) = 0. - R. J. Mathar, Apr 02 2017

Conjecture: (n+3)*(n+2)*a(n) - 4*(n^2+3*n+1)*a(n-1) + 16*(-n^2+n+1)*a(n-2) + 64*(n-1)*(n-2)*a(n-3) = 0. - R. J. Mathar, Apr 02 2017

a(n) = Sum_{k=0..floor(n/2)} n!/(k!*k!*(floor(n/2)-k)!*(floor((n+1)/2)-k)!*(k+1)) (conjectured). - Roger Ford, Aug 04 2017

a(n) = A000108(floor((n+1)/2))*A000108(floor(n/2))*(2*(floor(n/2))+1). - Roger Ford, Nov 15 2019

a(n) = Product_{k=3..n} (4*floor((k-1)/2) + 2) / (floor((k+2)/2)). - Roger Ford, Apr 29 2024