A054474 - OEIS

%I #89 Nov 11 2024 10:25:45

%S 1,4,20,176,1876,22064,275568,3584064,47995476,657037232,9150655216,

%T 129214858304,1845409805168,26606114089024,386679996988736,

%U 5658611409163008,83302885723872852,1232764004638179504,18327520881735288432,273595871825723062848

%N Number of walks on square lattice that start and end at origin after 2n steps, not touching origin at intermediate stages.

%C 1-dimensional and 3-dimensional analogs are A002420 and A049037.

%C Trajectories returning to the origin are prohibited, contrary to the situation in A094061.

%C The probability of returning to the origin for the first time after 2n steps is given by a(n)/4^(2*n). If A(x) is a generating function for this sequence, A(x/16) is a generating function for the sequence of probabilities. The sum of these probabilities for n > 0 is 1 unlike in dimensions > 2. - _Shel Kaphan_, Feb 13 2023

%D S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 322-331.

%H Alois P. Heinz, <a href="/A054474/b054474.txt">Table of n, a(n) for n = 0..834</a>

%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/polya/flajolet.html">Symmetric Random Walk on n-Dimensional Integer Lattice</a> [Broken link]

%H Steven R. Finch, <a href="/A054474/a054474.txt">Symmetric Random Walk on n-Dimensional Integer Lattice</a> [Cached copy, with permission of the author]

%H Markus Kuba and Alois Panholzer, <a href="https://arxiv.org/abs/2411.03930">Lattice paths and the diagonal of the cube</a>, arXiv:2411.03930 [math.CO], 2024. See p. 14.

%F G.f.: 2 - AGM(1, (1-16*x)^(1/2)).

%F G.f.: 2 - 1/hypergeom([1/2,1/2],[1],16*x). - _Joerg Arndt_, Jun 16 2011

%F Let (in Maple notation) G(x):=4/Pi*EllipticK(4*t)-2/Pi*EllipticF(1/sqrt(2+4*t), 4*t)-2/Pi*EllipticF(1/sqrt(2-4*t), 4*t), then GenFunc(x):=2-1/G(x). - _Sergey Perepechko_, Sep 11 2004

%F G.f.: 2 - Pi/(2*EllipticK(4*sqrt(x))). - _Vladeta Jovovic_, Jun 23 2005

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

%F INVERTi transform of A002894. - _R. J. Mathar_, Sep 24 2020

%e a(5)=22064, i.e., there are 22064 different walks (on a square lattice) that start and end at the origin after 2*5=10 steps, avoiding the origin at intermediate steps.

%p b:= proc(n) b(n):= binomial(2*n, n)^2 end:

%p a:= proc(n) option remember;

%p       b(n)-add(a(n-i)*b(i), i=1..n-1)

%p     end:

%p seq(a(n), n=0..21);  # _Alois P. Heinz_, Dec 05 2023

%t m = 18; gf[x_] = 2 - Pi/(2*EllipticK[4*Sqrt[x]]); (List @@ Normal[ Series[ gf[x], {x, 0, m-1}]] /. x -> 1)[[1 ;; m+1]]*Table[4^k, {k, 0, m}] (* _Jean-François Alcover_, Jun 16 2011, after _Vladeta Jovovic_ *)

%t CoefficientList[Series[2-Pi/(2*EllipticK[16*x]),{x,0,20}],x] (* _Vaclav Kotesovec_, Mar 10 2014 *)

%t CoefficientList[Series[2-ArithmeticGeometricMean[1,Sqrt[1-16x]],{x,0,20}],x] (* _Thomas Dybdahl Ahle_, Oct 30 2023 *)

%o (PARI) a(n)=if(n<0,0,polcoeff(2-agm(1,sqrt(1-16*x+x*O(x^n))),n))

%Y Cf. A002894, A002420, A049037, A063887.

%Y Column k=2 of A361397.

%K easy,nonn,walk

%O 0,2

%A Alessandro Zinani (alzinani(AT)tin.it), May 19 2000