login
This site is supported by donations to The OEIS Foundation.

 

Logo


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],[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

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

N. J. A. Sloane

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.

License Agreements, Terms of Use, Privacy Policy. .

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