cp's OEIS Frontend

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

%I A005558 M2598 #167 Apr 19 2025 03:24:31
%S A005558 1,1,3,6,20,50,175,490,1764,5292,19404,60984,226512,736164,2760615,
%T A005558 9202050,34763300,118195220,449141836,1551580888,5924217936,
%U A005558 20734762776,79483257308,281248448936,1081724803600,3863302870000,14901311070000,53644719852000
%N A005558 a(n) is the number of n-step walks on square lattice such that 0 <= y <= x at each step.
%C A005558 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
%C A005558 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
%C A005558 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
%D A005558 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005558 Alois P. Heinz, <a href="/A005558/b005558.txt">Table of n, a(n) for n = 0..1000</a>
%H A005558 Alin Bostan, <a href="https://www-apr.lip6.fr/sem-comb-slides/IHP-bostan.pdf">Computer Algebra for Lattice Path Combinatorics</a>, Slides for Séminaire de Combinatoire Ph. Flajolet, Mar 28 2013.
%H A005558 Alin Bostan, <a href="https://specfun.inria.fr/bostan/HDR.pdf">Calcul Formel pour la Combinatoire des Marches</a> [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, December 2017.
%H A005558 Alin Bostan, Frédéric Chyzak, Mark van Hoeij, Manuel Kauers, and Lucien Pech, <a href="https://doi.org/10.1016/j.ejc.2016.10.010">Hypergeometric expressions for generating functions of walks with small steps in the quarter plane</a>, Eur. J. Comb. 61, 242-275 (2017)
%H A005558 Sergi Elizalde, <a href="https://arxiv.org/abs/2002.12874">The degree of symmetry of lattice paths</a>, arXiv:2002.12874 [math.CO], 2020.
%H A005558 R. K. Guy, <a href="/A005555/a005555.pdf">Letter to N. J. A. Sloane, May 1990</a>
%H A005558 R. K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, Sandsteps and Pascal Pyramids</a>, J. Integer Seqs., Vol. 3 (2000), #00.1.6. See Column 1 of Figure 5.
%H A005558 Heinrich Niederhausen, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Niederhausen/niederhausen10.html">A Note on the Enumeration of Diffusion Walks in the First Octant by Their Number of Contacts with the Diagonal</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.3.
%F A005558 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
%F A005558 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
%F A005558 E.g.f (conjectured): BesselI(1,2*x)*(BesselI(0,2*x)+BesselI(1,2*x))/x. - _Benjamin Phillabaum_, Feb 25 2011
%F A005558 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
%F A005558 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
%F A005558 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
%F A005558 a(n) = A000108(floor((n+1)/2))*A000108(floor(n/2))*(2*(floor(n/2))+1). - _Roger Ford_, Nov 15 2019
%F A005558 a(n) = Product_{k=3..n} (4*floor((k-1)/2) + 2) / (floor((k+2)/2)). - _Roger Ford_, Apr 29 2024
%p A005558 A:= proc(n,x,y) option remember;
%p A005558     local j, xpyp, xp,yp, res;
%p A005558     xpyp:= [[x-1,y],[x+1,y],[x,y-1],[x,y+1]];
%p A005558     res:= 0;
%p A005558     for j from 1 to 4 do
%p A005558       xp:= xpyp[j,1];
%p A005558       yp:= xpyp[j,2];
%p A005558       if xp < 0 or xp > yp or xp + yp > n then next fi;
%p A005558       res:= res + procname(n-1,xp,yp)
%p A005558     od;
%p A005558 return res
%p A005558 end proc:
%p A005558 A(0,0,0) := 1:
%p A005558 seq(add(add(A(n,x,y), y = x .. n - x), x = 0 .. floor(n/2)), n = 0 .. 50); # _Robert Israel_, Oct 07 2015
%t A005558 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 *)
%o A005558 (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))
%o A005558 (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
%o A005558 (Python)
%o A005558 from sympy import ceiling as c, binomial
%o A005558 def a(n):
%o A005558     return binomial(n + 1, c(n/2))*binomial(n, n//2) - binomial(n + 1, c((n - 1)/2))*binomial(n, (n - 1)//2)
%o A005558 print([a(n) for n in range(51)]) # _Indranil Ghosh_, Jul 02 2017
%Y A005558 See A138350 for a signed version.
%Y A005558 Bisections are A000891 and A000888/2.
%Y A005558 Cf. A005559, A005560, A005561, A005562, A093768.
%Y A005558 Cf. A000108, A005817. Column y=0 of A052174.
%K A005558 nonn,walk
%O A005558 0,3
%A A005558 _N. J. A. Sloane_