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,2

Comments

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

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000

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

Example

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.

Mathematica

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

Prog

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

Crossrefs

Sequence in context: A282023 A149376 A149377 * A149378 A149379 A149380

Adjacent sequences: A063884 A063885 A063886 * A063888 A063889 A063890

Keyword

nonn

Author

Henry Bottomley, Aug 28 2001

Extensions

a(23) corrected by Jean-François Alcover, Jun 02 2019

Status

approved