cp's OEIS Frontend

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

%I A054474 #89 Nov 11 2024 10:25:45
%S A054474 1,4,20,176,1876,22064,275568,3584064,47995476,657037232,9150655216,
%T A054474 129214858304,1845409805168,26606114089024,386679996988736,
%U A054474 5658611409163008,83302885723872852,1232764004638179504,18327520881735288432,273595871825723062848
%N A054474 Number of walks on square lattice that start and end at origin after 2n steps, not touching origin at intermediate stages.
%C A054474 1-dimensional and 3-dimensional analogs are A002420 and A049037.
%C A054474 Trajectories returning to the origin are prohibited, contrary to the situation in A094061.
%C A054474 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 A054474 S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 322-331.
%H A054474 Alois P. Heinz, <a href="/A054474/b054474.txt">Table of n, a(n) for n = 0..834</a>
%H A054474 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 A054474 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 A054474 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 A054474 G.f.: 2 - AGM(1, (1-16*x)^(1/2)).
%F A054474 G.f.: 2 - 1/hypergeom([1/2,1/2],[1],16*x). - _Joerg Arndt_, Jun 16 2011
%F A054474 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 A054474 G.f.: 2 - Pi/(2*EllipticK(4*sqrt(x))). - _Vladeta Jovovic_, Jun 23 2005
%F A054474 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 A054474 INVERTi transform of A002894. - _R. J. Mathar_, Sep 24 2020
%e A054474 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 A054474 b:= proc(n) b(n):= binomial(2*n, n)^2 end:
%p A054474 a:= proc(n) option remember;
%p A054474       b(n)-add(a(n-i)*b(i), i=1..n-1)
%p A054474     end:
%p A054474 seq(a(n), n=0..21);  # _Alois P. Heinz_, Dec 05 2023
%t A054474 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 A054474 CoefficientList[Series[2-Pi/(2*EllipticK[16*x]),{x,0,20}],x] (* _Vaclav Kotesovec_, Mar 10 2014 *)
%t A054474 CoefficientList[Series[2-ArithmeticGeometricMean[1,Sqrt[1-16x]],{x,0,20}],x] (* _Thomas Dybdahl Ahle_, Oct 30 2023 *)
%o A054474 (PARI) a(n)=if(n<0,0,polcoeff(2-agm(1,sqrt(1-16*x+x*O(x^n))),n))
%Y A054474 Cf. A002894, A002420, A049037, A063887.
%Y A054474 Column k=2 of A361397.
%K A054474 easy,nonn,walk
%O A054474 0,2
%A A054474 Alessandro Zinani (alzinani(AT)tin.it), May 19 2000