This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A005558 a(n) is the number of n-step walks on square lattice such that 0 <= y <= x at each step. (Formerly M2598) 12
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 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 A. Bostan, Computer Algebra for Lattice Path Combinatorics, Slides for Séminaire de Combinatoire Ph. Flajolet, Mar 28 2013. 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. 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],,16*x^2)+2*x*(4*x-1)*hypergeom([3/2, 3/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 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 *) PROG (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)) (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 (Python) from sympy import ceiling as c, binomial, floor def a(n): return binomial(n + 1, c(n/2))*binomial(n, floor(n/2)) - binomial(n + 1, c((n - 1)/2))*binomial(n, floor((n - 1)/2)) print [a(n) for n in xrange(51)] # Indranil Ghosh, Jul 02 2017 CROSSREFS See A138350 for a signed version. Bisections are A000891 and A000888/2. Cf. A005559, A005560, A005561, A005562, A093768. Sequence in context: A052408 A148573 A148574 * A138350 A148575 A148576 Adjacent sequences:  A005555 A005556 A005557 * A005559 A005560 A005561 KEYWORD nonn,walk,changed AUTHOR 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 20 02:34 EST 2019. Contains 329323 sequences. (Running on oeis4.)