A063887 Number of n-step walks on a square lattice starting from the origin but not returning to it at any stage.
1, 4, 12, 48, 172, 688, 2576, 10304, 39340, 157360, 607376, 2429504, 9442448, 37769792, 147495104, 589980416, 2311926188, 9247704752, 36333781776, 145335127104, 572189853200, 2288759412800, 9025822792896, 36103291171584, 142567754881168, 570271019524672, 2254477964009664, 9017911856038656
Offset: 0
Keywords
Examples
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.
Links
- Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
Programs
-
Mathematica
CoefficientList[ Pi/(2 (1 - 4 x) EllipticK[16 x^2]) + O[x]^25, x] (* Jean-François Alcover, Jun 02 2019 *)
-
PARI
my(x='x+O('x^33)); Vec( agm(1, (1+4*x)/(1-4*x)) ) \\ Joerg Arndt, May 17 2019
Formula
a(2n) = 4*a(2n-1) - A054474(n); a(2n+1) = 4*a(2n).
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
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
Extensions
a(23) corrected by Jean-François Alcover, Jun 02 2019
Comments