A063887 -id:A063887 - 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.

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

Offset: 0

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

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

			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.

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

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.

Cf. A002894, A002420, A049037, A063887.

Column k=2 of A361397.

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

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 *)

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

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

A098981 Total number of self-intersections of all n-step walks on the square lattice starting at the origin.

Original entry on oeis.org

0, 0, 4, 32, 212, 1184, 6256, 31104, 150612, 707232, 3270128, 14845312, 66716016, 296203136, 1305752896, 5706772992, 24810133076, 107172696736, 461076481904, 1973848707456, 8422716604400, 35800153515904, 151766977315136, 641333362266624, 2704240670895984

Offset: 0

Pietro Monari (Pietro.Monari(AT)tetrapak.com), Oct 24 2004

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A098982, A002894, A063887.

seq(n)={my(u=Vec(agm(1, (1+4*x)/(1-4*x) + O(x*x^n))), v=vector(#u)); for(i=1, n, v[1+i] = 4*v[i] + 4^i - u[1+i]); v} \\ Andrew Howroyd, Aug 09 2025

seq(n)={Vec(1/(1-4*x)^2 - agm(1, (1+4*x)/(1-4*x) + O(x*x^n))/(1-4*x), -n-1)} \\ Andrew Howroyd, Aug 09 2025

Analysis of this sequence and A098982: Let a(n)= total number of self-intersections of all walks on a lattice starting from the origin. Recursions:
a(n) = r * a(n-1) + w(n) - b(n); a(0)=0; or a(n) = r * a(n-1) + Sum_{m=0..n-1} b(m) q(n-m); a(0)=0;
where w(n) = number of n-steps walks on the lattice, q(n) = number of n-steps walks ending in the origin, b(n) = number of n-steps walks that never go back to the origin, r = valency. The convolution of b(n) and q(n) gives w(n).
On the square lattice: w(n) = 4^n, q(n) is A002894 alternated with 0 in odd positions: 1, 0, 4, 0, 36, 0, 400, ...; q(2k) = binomial(2k, k)^2, q(2k+1) = 0; b(n) is A063887: 1, 4, 12, 48, 172, 688, ...
G.f.'s: a(n) -> C(x), b(n) -> B(x), q(n) -> Q(x) is K(4x)/(pi/2) with K(z)= complete elliptic integral first kind at z, w(n) -> W(x) = 1/(1-4x).
We find b(n) as the sequence which convoluted with q(n) gives w(n): W(x) = B(x)*Q(x) => B(x) = 1/((1 - 4x) Q(x)); C(x/4)=x C(x/4) +1/(1-x) - B(x/4) -1 = (1-x)^(-2)*x-1/Q(x/4)).
This machinery works an any lattice with the appropriate b(n), w(n) and q(n).
G.f.: 1/(1 - 4*x)^2 - B(x)/(1 - 4*x) where B(x) is the g.f. of A063887. - Andrew Howroyd, Aug 09 2025

a(7) onwards from Andrew Howroyd, Aug 09 2025

A248169 G.f.: AGM( (1-x)/(1+x), (1+3x)/(1-3x) ).

Original entry on oeis.org

1, 2, 6, 18, 46, 146, 398, 1234, 3454, 10610, 30230, 92290, 265670, 808210, 2343182, 7110994, 20720798, 62774578, 183617910, 555559554, 1629845726, 4926370114, 14486707710, 43752525762, 128909169334, 389075915954, 1148184115062, 3463595977986, 10235096852902

Offset: 0

Paul D. Hanna, Oct 03 2014

nonn

Here AGM(x,y) = AGM((x+y)/2,sqrt(x*y)) is the arithmetic-geometric mean.
a(n) == 2 (mod 4) for n>0.
Limit a(n+1)/a(n) = 3.

			G.f.: A(x) = 1 + 2*x + 6*x^2 + 18*x^3 + 46*x^4 + 146*x^5 + 398*x^6 +...

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

Cf. A063887.

CoefficientList[Series[Pi*(1 + 3*x)/((2*(1 - 3*x)*EllipticK[(16*x*(1 + 3*x^2)) / ((1 + x)^2*(1 + 3*x)^2)])), {x, 0, 30}], x] (* Vaclav Kotesovec, Sep 26 2019 *)

{a(n)=local(A,X=x+x*O(x^n));A=agm((1-x)/(1+X),(1+3*x)/(1-3*X)); polcoeff(A,n)}
for(n=0,40,print1(a(n),", "))

a(n) ~ Pi * 3^n / log(n) * (1 - (gamma + 4*log(2))/log(n) + (gamma^2 + 8*log(2)*gamma + 16*log(2)^2 - Pi^2/6) / log(n)^2), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Sep 30 2019

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A098981 Total number of self-intersections of all n-step walks on the square lattice starting at the origin.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A248169 G.f.: AGM( (1-x)/(1+x), (1+3x)/(1-3x) ).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A098981 Total number of self-intersections of all n-step walks on the square lattice starting at the origin.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A248169 G.f.: AGM( (1-x)/(1+x), (1+3*x)/(1-3*x) ).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A248169 G.f.: AGM( (1-x)/(1+x), (1+3x)/(1-3x) ).