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

1, 4, 20, 176, 1876, 22064, 275568, 3584064, 47995476, 657037232, 9150655216, 129214858304, 1845409805168, 26606114089024, 386679996988736, 5658611409163008, 83302885723872852, 1232764004638179504, 18327520881735288432, 273595871825723062848

Offset: 0

Author

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

Keywords

• easy
• nonn
• walk

Comments

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

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

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

Examples

			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.
		

References

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..834
• S. R. Finch, Symmetric Random Walk on n-Dimensional Integer Lattice [Broken link]
• Steven R. Finch, Symmetric Random Walk on n-Dimensional Integer Lattice [Cached copy, with permission of the author]
• Markus Kuba and Alois Panholzer, Lattice paths and the diagonal of the cube, arXiv:2411.03930 [math.CO], 2024. See p. 14.

Crossrefs

Cf. A002894, A002420, A049037, A063887.

Column k=2 of A361397.

Programs

Maple

b:= proc(n) b(n):= binomial(2*n, n)^2 end:
a:= proc(n) option remember;
      b(n)-add(a(n-i)*b(i), i=1..n-1)
    end:
seq(a(n), n=0..21);  # Alois P. Heinz, Dec 05 2023

Mathematica

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 *)
CoefficientList[Series[2-Pi/(2*EllipticK[16*x]),{x,0,20}],x] (* Vaclav Kotesovec, Mar 10 2014 *)
CoefficientList[Series[2-ArithmeticGeometricMean[1,Sqrt[1-16x]],{x,0,20}],x] (* Thomas Dybdahl Ahle, Oct 30 2023 *)

PARI

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

Formula

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

G.f.: 2 - 1/hypergeom([1/2,1/2],[1],16*x). - Joerg Arndt, Jun 16 2011

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

G.f.: 2 - Pi/(2*EllipticK(4*sqrt(x))). - Vladeta Jovovic, Jun 23 2005

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

INVERTi transform of A002894. - R. J. Mathar, Sep 24 2020