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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A260153 Number of walks of length n on the square lattice (with steps N, E, S, W) that start at (0,0) and avoid the West quadrant {(i,j): i < -|j|}. 2
1, 3, 12, 41, 164, 590, 2360, 8715, 34860, 130776, 523104, 1983212, 7932848, 30303416, 121213664, 465673065, 1862692260, 7187760140, 28751040560, 111338982436, 445355929744, 1729672999418, 6918691997672, 26936111629934, 107744446519736, 420338301077100 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

M. Bousquet-Mélou, Plane lattice walks avoiding a quadrant, arXiv:1511.02111 [math.CO], 2015.

FORMULA

G.f.: -1/(4*t) + (1+4*t) * ((sc(K(4*t)/3;4*t)+nc(K(4*t)/3;4*t))/sqrt(3-48*t^2) - K(4*t)/(2*Pi)) / (3*t), where K(4*t) is the complete elliptic integral of modulus 4*t and sc(.;4*t), nc(.;4*t) are Jacobi elliptic functions again with modulus 4*t. - Timothy Budd, Oct 23 2016

EXAMPLE

For n=1, the three possible walks are N, E, S.

MAPLE

b:= proc(n, i, j) option remember;

      if i < -abs(j) then 0

    elif n=0 then 1

    else b(n-1, i-1, j)+

         b(n-1, i+1, j)+

         b(n-1, i, j-1)+

         b(n-1, i, j+1)

      fi

    end:

a:= n-> b(n, 0, 0);

seq(a(n), n=0..30);  # Alois P. Heinz, Nov 09 2015

# second Maple program:

a:= proc(n) option remember; `if`(n<4, [1, 3, 12, 41][n+1],

      ((4*(2*n-5))*(12*n^4-16*n^3-6*n^2+10*n+3) *a(n-1)

      +(16*(2*n-5))*(2*n+1)*(6*n^4-24*n^3+28*n^2-8*n-3) *a(n-2)

      -(64*(2*n+1))*(12*n^4-80*n^3+186*n^2-178*n+63) *a(n-3)

      -(256*(n-1))*(2*n+1)*(2*n-1)*(3*n-7)*(n-3)^2 *a(n-4))/

      ((2*n-3)*(2*n-5)*(n-1)*(3*n+1)*(n+1)^2))

    end:

seq(a(n), n=0..30);  # Alois P. Heinz, Nov 09 2015

MATHEMATICA

b[n_, i_, j_] := b[n, i, j] = Which[i < -Abs[j], 0, n == 0, 1, True, b[n-1, i-1, j] + b[n-1, i+1, j] + b[n-1, i, j-1] + b[n-1, i, j+1]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 01 2016, after Alois P. Heinz *)

With[{n = 10}, CoefficientList[Series[

-1/(4*t) + (1+4*t)*((sc+Sqrt[1+sc^2])/Sqrt[3-48*t^2] - k/(2*Pi))/(3*t)

  /. sc -> Pi*Sqrt[3]*Normal[Sum[(-1)^p/(1 + q^(-2*p) + q^(2*p)), {p, -n, n}]  + O[q]^(2*n)]/(2*k*Sqrt[1-16*t^2])

  /. q -> EllipticNomeQ[16*t^2] /. k -> EllipticK[16*t^2],

{t, 0, 4*n}], t]] (* Timothy Budd, Oct 23 2016 *)

CROSSREFS

Cf. A060898 for walks avoiding the negative quadrant rather than the West one, A260154.

Sequence in context: A127120 A017940 A038342 * A135264 A084529 A017941

Adjacent sequences:  A260150 A260151 A260152 * A260154 A260155 A260156

KEYWORD

nonn

AUTHOR

Mireille Bousquet-Mélou, Nov 09 2015

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 August 20 10:17 EDT 2019. Contains 326149 sequences. (Running on oeis4.)