OFFSET
0,3
COMMENTS
a(n) = number of walks in Z^4 starting and ending at the origin, using only the steps (a,b,0,0), (a,0,b,0), ..., (0,0,a,b), where a,b can be +1 or -1.
LINKS
Christoph Koutschan, Table of n, a(n) for n = 0..729
D. Broadhurst, Bessel moments, random walks and Calabi-Yau equations.
A. J. Guttmann, Lattice Green's functions in all dimensions, J. Phys. A: Math. Theor. 43 (2010), 305205.
C. Koutschan, Computations for higher-dimensional fcc lattices.
C. Koutschan, Lattice Green's Functions of the Higher-Dimensional Face-Centered Cubic Lattices, arXiv:1108.2164 [math.CO], 2011-2013.
C. Koutschan, Lattice Green's functions of the higher-dimensional face-centered cubic lattices, J. Phys. A: Math. Theor. 46(12) (2013), 125005.
FORMULA
a(n) satisfies the fifth-order linear recurrence equation (35*n^2-70*n+27)*n^4*a(n) +(n-1)*(105*n^5-315*n^4+151*n^3 +487*n^2 -540*n+144)*a(n-1) -8*(1750*n^6-10500*n^5+25150*n^4 -29745*n^3 +17065*n^2-3738*n+72)*a(n-2) -144*(n-2) *(1225*n^5-7350*n^4 +15435*n^3 -11430*n^2-352*n+1440)*a(n-3)-6912*(n-3)*(n-2)*(105*n^4 -525*n^3+676*n^2 +62*n-132)*a(n-4)-27648*(n-4)*(n-3)^2*(n-2)*(35*n^2-8) *a(n-5) = 0.
The generating function P(z) = Sum_{n>=0} a(n)*(z/24)^n is given by the 4-fold integral (1/Pi)^4 Int_{0..Pi} ... Int_{0..Pi} 1/(1-z*lambda_4) dk_1 ... dk_4, where the structure function is defined as lambda_4 = (1/binomial(4,2)) Sum_{i=1..4} Sum_{j=(i+1)..4} cos(k_i)*cos(k_j). The function P(z) satisfies the fourth-order linear ODE 12*z*(256+632*z+702*z^2+382*z^3+98*z^4+9*z^5)*P(z)+12*(-384+224*z+3716*z^2+7633*z^3 +6734*z^4+2939*z^5+604*z^6+45*z^7) *P'(z)+6*z*(-5376-5248*z+11080*z^2 +25286*z^3 +19898*z^4+7432*z^5 +1286*z^6+81*z^7) *P''(z)+2*z^2*(4+3*z)*(-3456-2304*z+3676*z^2+4920 *z^3+2079*z^4+356*z^5 +21*z^6)*P'''(z)+(-1+z)*z^3*(2+z)*(3+z)*(6+z)*(8+z)*(4+3*z)^2*P''''(z) = 0.
a(n) ~ 2^(3*n+1) * 3^n / (Pi^2 * n^2). - Vaclav Kotesovec, Apr 08 2016
EXAMPLE
There is one walk with no steps.
No walk with a single steps returns to the origin.
The number of returning walks with two steps is exactly the number of allowed steps (called the coordination number of the lattice): a(2) = 4*binomial(4,2).
MAPLE
nmax := 50: tt := [seq([seq(add(binomial(2*p, p)*binomial(2*j, 2*p-n)*binomial(2*n+2*j-2*p, n+j-p), p = floor((n+1)/2)..floor((n+2*j)/2)), j = 0..floor((nmax-n)/2))], n = 0..nmax)]: for d1 from 3 to 4 do tt := [seq([seq(add(binomial(n, p)*add(binomial(2*j, 2*q-p)*binomial(2*j+2*p-2*q, j+p-q)*tt[n-p+1, q+1], q = floor((p+1)/2)..floor((p+2*j)/2)), p = 0..n), j = 0..floor((nmax-n)/2))], n = 0..nmax)]: od: [seq(tt[n+1, 1], n = 0..nmax)];
MATHEMATICA
a[0] = 1; a[1] = 0; a[2] = 24; a[3] = 192; a[4] = 3384; a[n_] := a[n] = (27648*(-4 + n)*(-3 + n)^2*(-2 + n)*(-8 + 35*n^2)*a[-5 + n] + 6912*(-3 + n)*(-2 + n)*(-132 + 62*n + 676*n^2 - 525*n^3 + 105*n^4)*a[-4 + n] + 144*(-2 + n)*(1440 - 352*n - 11430*n^2 + 15435*n^3 - 7350*n^4 + 1225*n^5)*a[-3 + n] + 8*(72 - 3738*n + 17065*n^2 - 29745*n^3 + 25150*n^4 - 10500*n^5 + 1750*n^6)*a[-2 + n] - (-1 + n)*(144 - 540*n + 487*n^2 + 151*n^3 - 315*n^4 + 105*n^5)*a[-1 + n])/(n^4*(27 - 70*n + 35*n^2)); Array[a, 30, 0]
nmax = 50; T = Table[Sum[Binomial[2 p, p]*Binomial[2 j, 2 p - n]*Binomial[2 n + 2 j - 2 p, n + j - p], {p, Floor[(n + 1)/2], Floor[(n + 2 j)/2]}], {n, 0, nmax}, {j, 0, Floor[(nmax - n)/2]}]; Do[T = Table[Sum[Binomial[n, p]*Sum[Binomial[2 j, 2 q - p]*Binomial[2 j + 2 p - 2 q, j + p - q]*T[[n - p + 1, q + 1]], {q, Floor[(p + 1)/2], Floor[(p + 2 j)/2]}], {p, 0, n}], {n, 0, nmax}, {j, 0, If[d1 < 4, Floor[(nmax - n)/2], 0]}], {d1, 3, 4}]; First /@ T
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Christoph Koutschan, Apr 07 2016
STATUS
approved