|
%I M2598 #149 Dec 11 2022 14:29:04
%S 1,1,3,6,20,50,175,490,1764,5292,19404,60984,226512,736164,2760615,
%T 9202050,34763300,118195220,449141836,1551580888,5924217936,
%U 20734762776,79483257308,281248448936,1081724803600,3863302870000,14901311070000,53644719852000
%N a(n) is the number of n-step walks on square lattice such that 0 <= y <= x at each step.
%C 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 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 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 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A005558/b005558.txt">Table of n, a(n) for n = 0..1000</a>
%H A. 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 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 Bostan, Alin ; Chyzak, Frédéric; van Hoeij, Mark; Kauers, Manuel; Pech, Lucien <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 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 R. K. Guy, <a href="/A005555/a005555.pdf">Letter to N. J. A. Sloane, May 1990</a>
%H 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 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 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 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 E.g.f (conjectured): BesselI(1,2*x)*(BesselI(0,2*x)+BesselI(1,2*x))/x. - _Benjamin Phillabaum_, Feb 25 2011
%F 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 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 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 a(n) = A000108(floor((n+1)/2))*A000108(floor(n/2))*(2*(floor(n/2))+1). - _Roger Ford_, Nov 15 2019
%p A:= proc(n,x,y) option remember;
%p local j, xpyp, xp,yp, res;
%p xpyp:= [[x-1,y],[x+1,y],[x,y-1],[x,y+1]];
%p res:= 0;
%p for j from 1 to 4 do
%p xp:= xpyp[j,1];
%p yp:= xpyp[j,2];
%p if xp < 0 or xp > yp or xp + yp > n then next fi;
%p res:= res + procname(n-1,xp,yp)
%p od;
%p return res
%p end proc:
%p A(0,0,0) := 1:
%p 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 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 (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 (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 (Python)
%o from sympy import ceiling as c, binomial
%o def a(n):
%o return binomial(n + 1, c(n/2))*binomial(n, n//2) - binomial(n + 1, c((n - 1)/2))*binomial(n, (n - 1)//2)
%o print([a(n) for n in range(51)]) # _Indranil Ghosh_, Jul 02 2017
%Y See A138350 for a signed version.
%Y Bisections are A000891 and A000888/2.
%Y Cf. A005559, A005560, A005561, A005562, A093768.
%Y Cf. A000108, A005817.
%K nonn,walk
%O 0,3
%A _N. J. A. Sloane_
|
