login
Number of n-step walks on a square lattice starting from the origin but not returning to it at any stage.
4

%I #29 Sep 29 2019 13:09:03

%S 1,4,12,48,172,688,2576,10304,39340,157360,607376,2429504,9442448,

%T 37769792,147495104,589980416,2311926188,9247704752,36333781776,

%U 145335127104,572189853200,2288759412800,9025822792896,36103291171584,142567754881168,570271019524672,2254477964009664,9017911856038656

%N Number of n-step walks on a square lattice starting from the origin but not returning to it at any stage.

%C a(n)/4^n tends to zero as n increases.

%H Vaclav Kotesovec, <a href="/A063887/b063887.txt">Table of n, a(n) for n = 0..1000</a>

%F a(2n) = 4*a(2n-1) - A054474(n); a(2n+1) = 4*a(2n).

%F G.f.: agm(1, (1+4*x)/(1-4*x)), where agm(x,y) = agm((x+y)/2,sqrt(x*y)) is the arithmetic-geometric mean. - _Paul D. Hanna_, Oct 03 2014

%F a(n) ~ Pi * 4^n / log(n) * (1 - (gamma + 3*log(2)) / log(n) + (gamma^2 + 6*gamma*log(2) + 9*log(2)^2 - Pi^2/6) / log(n)^2), where gamma is the Euler-Mascheroni constant A001620. - _Vaclav Kotesovec_, Sep 29 2019

%e a(2)=12 since there are 16 2-step walks but 4 of them involve a return to the origin at some stage; similarly a(3)=48 since there are 64 3-step walks but 16 of them involve a return to the origin at some stage.

%t CoefficientList[ Pi/(2 (1 - 4 x) EllipticK[16 x^2]) + O[x]^25, x] (* _Jean-François Alcover_, Jun 02 2019 *)

%o (PARI) my(x='x+O('x^33)); Vec( agm(1, (1+4*x)/(1-4*x)) ) \\ _Joerg Arndt_, May 17 2019

%K nonn

%O 0,2

%A _Henry Bottomley_, Aug 28 2001

%E a(23) corrected by _Jean-François Alcover_, Jun 02 2019