cp's OEIS Frontend

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

%I A098981 #13 Aug 09 2025 20:07:12
%S A098981 0,0,4,32,212,1184,6256,31104,150612,707232,3270128,14845312,66716016,
%T A098981 296203136,1305752896,5706772992,24810133076,107172696736,
%U A098981 461076481904,1973848707456,8422716604400,35800153515904,151766977315136,641333362266624,2704240670895984
%N A098981 Total number of self-intersections of all n-step walks on the square lattice starting at the origin.
%H A098981 Andrew Howroyd, <a href="/A098981/b098981.txt">Table of n, a(n) for n = 0..1000</a>
%F A098981 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:
%F A098981 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;
%F A098981 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).
%F A098981 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, ...
%F A098981 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).
%F A098981 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)).
%F A098981 This machinery works an any lattice with the appropriate b(n), w(n) and q(n).
%F A098981 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
%o A098981 (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
%o A098981 (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
%Y A098981 Cf. A098982, A002894, A063887.
%K A098981 nonn
%O A098981 0,3
%A A098981 Pietro Monari (Pietro.Monari(AT)tetrapak.com), Oct 24 2004
%E A098981 a(7) onwards from _Andrew Howroyd_, Aug 09 2025