A098981 Total number of self-intersections of all n-step walks on the square lattice starting at the origin.
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
Keywords
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..1000
Programs
-
PARI
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 -
PARI
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
Formula
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
Extensions
a(7) onwards from Andrew Howroyd, Aug 09 2025