A359801 Number of 4-dimensional cubic lattice walks that start and end at origin after 2n steps, not touching origin at intermediate stages.

1, 8, 104, 2944, 108136, 4525888, 204981888, 9792786432, 486323201640, 24874892400064, 1302278744460352, 69474942954714112, 3764568243058030208, 206675027529594291200, 11473858525271117889536, 643154944963894079717376, 36355546411928157876528744, 2070313613815122857027563200

Offset: 0

Author

Shel Kaphan, Mar 08 2023

Keywords

• nonn
• walk

Comments

In Novak's note it is mentioned that if P(z) and Q(z) are the g.f.s for the probabilities of indecomposable and decomposable loops, respectively, that P(z) = 1 - 1/Q(z). This works equally well using loop counts rather than probabilities. The g.f.s may be expressed by the series constructed from the sequences of counts of loops of length 2*n. Q(z) for the 4-d case is the series corresponding to A039699.

To obtain the probability of returning to the point of origin for the first time after 2*n steps, divide a(n) by the total number of walks of length 2*n in d dimensions: (2*d)^(2*n) = 64^n.

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..550
• Dorin Dumitraşcu and Liviu Suciu, Asymptotics for the Number of Random Walks in the Euclidean Lattice, arXiv:2212.01702 [math.CO], 2022, p.11.
• Jonathan Novak, Pólya's Random Walk Theorem, The American Mathematical Monthly, Vol. 121, No. 8 (October 2014), pp. 711-716.

Crossrefs

Cf. A039699, A287317 (number of walks that return to the origin in 2n steps).

Number of walks that return to the origin for the first time in 2n steps, in 1..3 dimensions: |A002420|, A054474, A049037.

Column k=4 of A361397.

Programs

Mathematica

walk4d[n_] :=
 Sum[(2 n)!/(i! j! k! (n - i - j - k)!)^2, {i, 0, n}, {j, 0,
   n - i}, {k, 0, n - i - j}]; invertSeq[seq_] :=
  CoefficientList[1 - 1/SeriesData[x, 0, seq, 0, Length[seq], 1], x]; invertSeq[Table[walk4d[n], {n, 0, 17}]]

PARI

seq(n) = {my(v=Vec(2 - 1/serlaplace(besseli(0, 2*x + O(x^(2*n+1)))^4))); vector(n+1, i, v[2*i-1])} \\ Andrew Howroyd, Mar 08 2023

Formula

G.f.: 2 - 1/Q(x) where Q(x) is the g.f. of A039699.

G.f.: 2 - 1/Integral_{t=0..oo} exp(-t)*BesselI(0,2*t*sqrt(x))^4 dt.

INVERTi transform of A039699.