|
%I #38 Oct 06 2019 05:00:38
%S 1,3,12,41,164,590,2360,8715,34860,130776,523104,1983212,7932848,
%T 30303416,121213664,465673065,1862692260,7187760140,28751040560,
%U 111338982436,445355929744,1729672999418,6918691997672,26936111629934,107744446519736,420338301077100
%N 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|}.
%H Alois P. Heinz, <a href="/A260153/b260153.txt">Table of n, a(n) for n = 0..1000</a>
%H M. Bousquet-Mélou, <a href="http://arxiv.org/abs/1511.02111">Plane lattice walks avoiding a quadrant</a>, arXiv:1511.02111 [math.CO], 2015.
%F 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
%F a(n) ~ Gamma(1/3) * 2^(2*n+2) / (3*Pi*n^(1/3)). - _Vaclav Kotesovec_, Oct 06 2019
%e For n=1, the three possible walks are N, E, S.
%p b:= proc(n,i,j) option remember;
%p if i < -abs(j) then 0
%p elif n=0 then 1
%p else b(n-1,i-1,j)+
%p b(n-1,i+1,j)+
%p b(n-1,i,j-1)+
%p b(n-1,i,j+1)
%p fi
%p end:
%p a:= n-> b(n,0,0);
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Nov 09 2015
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n<4, [1, 3, 12, 41][n+1],
%p ((4*(2*n-5))*(12*n^4-16*n^3-6*n^2+10*n+3) *a(n-1)
%p +(16*(2*n-5))*(2*n+1)*(6*n^4-24*n^3+28*n^2-8*n-3) *a(n-2)
%p -(64*(2*n+1))*(12*n^4-80*n^3+186*n^2-178*n+63) *a(n-3)
%p -(256*(n-1))*(2*n+1)*(2*n-1)*(3*n-7)*(n-3)^2 *a(n-4))/
%p ((2*n-3)*(2*n-5)*(n-1)*(3*n+1)*(n+1)^2))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Nov 09 2015
%t 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_ *)
%t With[{n = 10}, CoefficientList[Series[
%t -1/(4*t) + (1+4*t)*((sc+Sqrt[1+sc^2])/Sqrt[3-48*t^2] - k/(2*Pi))/(3*t)
%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])
%t /. q -> EllipticNomeQ[16*t^2] /. k -> EllipticK[16*t^2],
%t {t,0,4*n}], t]] (* _Timothy Budd_, Oct 23 2016 *)
%Y Cf. A060898 for walks avoiding the negative quadrant rather than the West one, A260154.
%K nonn
%O 0,2
%A _Mireille Bousquet-Mélou_, Nov 09 2015
|
