login
The OEIS is supported by the many generous donors 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
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
a(n) ~ Gamma(1/3) * 2^(2*n+2) / (3*Pi*n^(1/3)). - Vaclav Kotesovec, Oct 06 2019
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: A325482 A017940 A038342 * A328299 A135264 A358690
KEYWORD
nonn
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 15:38 EDT 2024. Contains 371254 sequences. (Running on oeis4.)