OFFSET
0,3
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).
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Pietro Monari (Pietro.Monari(AT)tetrapak.com), Oct 24 2004
STATUS
approved