A039699 Number of 4-dimensional cubic lattice walks that start and end at the origin after 2n steps, free to pass through origin at intermediate stages.

1, 8, 168, 5120, 190120, 7939008, 357713664, 16993726464, 839358285480, 42714450658880, 2225741588095168, 118227198981126144, 6380762273973278464, 349019710593278412800, 19310744204362333900800, 1079054103459778710405120, 60818479243449308702049960

Offset: 0

Author

Alessandro Zinani (alzinani(AT)tin.it)

Keywords

• nonn
• nice
• easy
• walk

Comments

Generating function G(x) is D-finite with a singular point at x = 1/64 (cf. Graph Link). After summing 300000 terms, G(1/64) = 1.239466... and 1 - 1/G(1/64) = 0.193201... Convergence to A086232 is very slow. - Bradley Klee, Aug 20 2018

a(n) is also the constant term in the expansion of (w + 1/w + x + 1/x + y + 1/y + z + 1/z)^(2n). This follows directly from the sequence name, each variable corresponding to a single step in one of the four axis directions. - Christopher J. Smyth, Sep 28 2018

Examples

			a(5)=7939008, i.e., there are 7939008 different walks that start and end at origin of a 4-dimensional integer lattice after 2*5=10 steps, free to pass through origin at intermediate steps.
		

References

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

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..557
• 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]
• S. Hassani, J.-M. Maillard, and N. Zenine, On the diagonals of rational functions: the minimal number of variables (unabridged version), arXiv:2502.05543 [math-ph], 2025. See pp. 33, 44.
• Bradley Klee, Graph of g.f.
• Gilbert Labelle and Annie Lacasse, Closed paths whose steps are roots of unity, in FPSAC 2011, Reykjavik, Iceland DMTCS proc. AO, 2011, 599-610.
• Yen Lee Loh, A general method for calculating lattice Green functions on the branch cut, arXiv:1706.03083 [math-ph], 2017.
• J. Novak, Pólya's random walk theorem, arXiv:1301.3916 [math.PR], 2013.

Crossrefs

1-dimensional, 2-dimensional, 3-dimensional analogs are A000984, A002894, A002896. Pólya Constant: A086232.

Row k=4 of A287318.

Programs

Maple

A039699 := n -> binomial(2*n,n)^2*hypergeom([1/2, -n, -n, -n],[1, 1, 1/2 - n], 1):
seq(simplify(A039699(n)), n=0..14); # Peter Luschny, May 23 2017

Mathematica

max = 30 (* must be even *); Partition[ CoefficientList[ Series[ BesselI[0, 2 x]^4, {x, 0, max}], x]*Range[0, max]!, 2][[All, 1]] (* Jean-François Alcover, Oct 05 2011 *)
With[{nn=30},Take[CoefficientList[Series[BesselI[0,2x]^4,{x,0,nn}],x] Range[0,nn]!,{1,-1,2}]] (* Harvey P. Dale, Aug 09 2013 *)
RecurrenceTable[{256*(n-1)^2*(2*n-3)*(2*n-1)*a[n-2] - 4*(2*n-1)^2*(5*n^2-5*n+2)*a[n-1] + n^4*a[n]==0, a[0]==1, a[1]==8}, a, {n,0,100}] (* Bradley Klee, Aug 20 2018 *)

PARI

C=binomial;
A002895(n) = sum(k=0,n, C(n,k)^2 * C(2*n-2*k,n-k) * C(2*k,k) );
a(n)= C(2*n,n) * A002895(n);
/* Joerg Arndt, Apr 19 2013 */

Python

from math import comb
def A039699(n): return comb(n<<1,n)*((sum(comb(n,k)**2*comb(n-k<<1,n-k)*comb(m:=k<<1,k) for k in range(n+1>>1))<<1) + (0 if n&1 else comb(n,n>>1)**4)) # Chai Wah Wu, Jun 17 2025

Formula

E.g.f.: Sum_{n>=0} a(2*n) * x^(2*n)/(2*n)! = I_0(2*x)^4. (I = Modified Bessel function of the first kind).

a(n) = binomial(2*n,n)*A002895(n). - Mark van Hoeij, Apr 19 2013

a(n) = binomial(2*n,n)^2*hypergeom([1/2,-n,-n,-n],[1,1,1/2-n],1). - Peter Luschny, May 23 2017

a(n) ~ 2^(6*n+1) / (Pi*n)^2. - Vaclav Kotesovec, Nov 13 2017

From Bradley Klee, Aug 20 2018: (Start)

G.f.: Define G(x) = Sum_{n>=0} a(n)*x^n and G^(j) = (d/dx)^j G(x), then Sum_{j=0..4,k=0..5} M_{j,k}*G^(j)*x^k = 0, with

M={{-8, 768, 0, 0, 0, 0}, {1, -424, 14592, 0, 0, 0}, {0, 7, -1172, 25344, 0, 0}, {0, 0, 6, -640, 10240, 0}, {0, 0, 0, 1, -80, 1024}}.

Sum_{j=0..2,k=0..4} M_{j,k}*a(n-j)*n^k = 0, with

M={{0, 0, 0, 0, 1}, {-8, 52, -132, 160, -80}, {768, -3584, 5888, -4096, 1024}}.

(End)

a(n) = Sum_{i+j+k+l=n, 0<=i,j,k,l<=n} multinomial(2n [i,i,j,j,k,k,l,l]). - Shel Kaphan, Jan 16 2023