A361397 -id:A361397 - cp's OEIS frontend

A054474 Number of walks on square lattice that start and end at origin after 2n steps, not touching origin at intermediate stages.

1, 4, 20, 176, 1876, 22064, 275568, 3584064, 47995476, 657037232, 9150655216, 129214858304, 1845409805168, 26606114089024, 386679996988736, 5658611409163008, 83302885723872852, 1232764004638179504, 18327520881735288432, 273595871825723062848

Offset: 0

Alessandro Zinani (alzinani(AT)tin.it), May 19 2000

1-dimensional and 3-dimensional analogs are A002420 and A049037.
Trajectories returning to the origin are prohibited, contrary to the situation in A094061.
The probability of returning to the origin for the first time after 2n steps is given by a(n)/4^(2*n). If A(x) is a generating function for this sequence, A(x/16) is a generating function for the sequence of probabilities. The sum of these probabilities for n > 0 is 1 unlike in dimensions > 2. - Shel Kaphan, Feb 13 2023

			a(5)=22064, i.e., there are 22064 different walks (on a square lattice) that start and end at the origin after 2*5=10 steps, avoiding the origin at intermediate steps.

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

Alois P. Heinz, Table of n, a(n) for n = 0..834
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]
Markus Kuba and Alois Panholzer, Lattice paths and the diagonal of the cube, arXiv:2411.03930 [math.CO], 2024. See p. 14.

Cf. A002894, A002420, A049037, A063887.

Column k=2 of A361397.

b:= proc(n) b(n):= binomial(2*n, n)^2 end:
a:= proc(n) option remember;
      b(n)-add(a(n-i)*b(i), i=1..n-1)
    end:
seq(a(n), n=0..21);  # Alois P. Heinz, Dec 05 2023

m = 18; gf[x_] = 2 - Pi/(2*EllipticK[4*Sqrt[x]]); (List @@ Normal[ Series[ gf[x], {x, 0, m-1}]] /. x -> 1)[[1 ;; m+1]]*Table[4^k, {k, 0, m}] (* Jean-François Alcover, Jun 16 2011, after Vladeta Jovovic *)
CoefficientList[Series[2-Pi/(2*EllipticK[16*x]),{x,0,20}],x] (* Vaclav Kotesovec, Mar 10 2014 *)
CoefficientList[Series[2-ArithmeticGeometricMean[1,Sqrt[1-16x]],{x,0,20}],x] (* Thomas Dybdahl Ahle, Oct 30 2023 *)

a(n)=if(n<0,0,polcoeff(2-agm(1,sqrt(1-16*x+x*O(x^n))),n))

G.f.: 2 - AGM(1, (1-16*x)^(1/2)).
G.f.: 2 - 1/hypergeom([1/2,1/2],[1],16*x). - Joerg Arndt, Jun 16 2011
Let (in Maple notation) G(x):=4/Pi*EllipticK(4*t)-2/Pi*EllipticF(1/sqrt(2+4*t), 4*t)-2/Pi*EllipticF(1/sqrt(2-4*t), 4*t), then GenFunc(x):=2-1/G(x). - Sergey Perepechko, Sep 11 2004
G.f.: 2 - Pi/(2*EllipticK(4*sqrt(x))). - Vladeta Jovovic, Jun 23 2005
a(n) ~ Pi * 16^n / (n * log(n)^2) * (1 - (2*gamma + 8*log(2)) / log(n) + (3*gamma^2 + 24*log(2)*gamma + 48*log(2)^2 - Pi^2/2) / log(n)^2), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Sep 29 2019
INVERTi transform of A002894. - R. J. Mathar, Sep 24 2020

A139271 a(n) = 2n(4*n-3).

Original entry on oeis.org

0, 2, 20, 54, 104, 170, 252, 350, 464, 594, 740, 902, 1080, 1274, 1484, 1710, 1952, 2210, 2484, 2774, 3080, 3402, 3740, 4094, 4464, 4850, 5252, 5670, 6104, 6554, 7020, 7502, 8000, 8514, 9044, 9590, 10152, 10730, 11324, 11934, 12560, 13202, 13860, 14534, 15224

Offset: 0

Omar E. Pol, Apr 26 2008

Sequence found by reading the line from 0, in the direction 0, 2, ..., in the square spiral whose vertices are the triangular numbers A000217. Opposite numbers to the members of A033585 in the same spiral.
Twice decagonal numbers (or twice 10-gonal numbers). - Omar E. Pol, May 15 2008
a(n) is the number of walks in a cubic lattice of n dimensions that reach the point of origin for the first time after 4 steps. - Shel Kaphan, Mar 20 2023

G. C. Greubel, Table of n, a(n) for n = 0..5000
Omar E. Pol, Determinacion geometrica de los numeros primos y perfectos.
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A000217, A014634, A014635, A033585, A033586, A033587, A035008, A051870, A069129, A085250, A139272, A139273, A139274, A139275, A139276, A139278, A139279, A139280, A139281, A139282.
Cf. A001107.
Cf. numbers of the form n*(n*k-k+4)/2 listed in A226488 (this sequence is the case k=16). - Bruno Berselli, Jun 10 2013
Row n=2 of A361397.

Table[8n^2-6n,{n,0,40}] (* or *) LinearRecurrence[{3,-3,1},{0,2,20},50] (* Harvey P. Dale, Sep 26 2016 *)

a(n)=2*n*(4*n-3) \\ Charles R Greathouse IV, Jun 17 2017

a(n) = 8*n^2 - 6*n.
Sequences of the form a(n) = 8*n^2 + c*n have generating functions x{c+8+(8-c)x} / (1-x)^3 and recurrence a(n) = 3a(n-1) - 3a(n-2) + a(n-3). The inverse binomial transform is 0, c+8, 16, 0, 0, ... (0 continued). This applies to A139271-A139278, positive or negative c. - R. J. Mathar, May 12 2008
a(n) = A001107(n)*2. - Omar E. Pol, May 15 2008
a(n) = 16*n + a(n-1) - 14 (with a(0)=0). - Vincenzo Librandi, Aug 03 2010
From G. C. Greubel, Jul 18 2017: (Start)
G.f.: (2*x)*(7*x+1)/(1-x)^3.
E.g.f.: (8*x^2 + 2*x)*exp(x). (End)
Sum_{n>=1} 1/a(n) = Pi/12 + log(2)/2. - Amiram Eldar, Mar 28 2023

Corrected by Harvey P. Dale, Sep 26 2016

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

Original entry on oeis.org

1, 6, 54, 996, 22734, 577692, 15680628, 445162392, 13055851998, 392475442092, 12029082873372, 374482032292008, 11808861461931492, 376406128925067528, 12108063535794336312, 392560994063887113744, 12814685828476778001726, 420836267423433182275404

Offset: 0

Alessandro Zinani (alzinani(AT)tin.it)

			a(5) = 577692 because there are 577692 different walks that start and end at the origin after 2*5=10 steps, avoiding origin at intermediate steps.

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

Alois P. Heinz, Table of n, a(n) for n = 0..200
Steven R. Finch, Symmetric Random Walk on n-Dimensional Integer Lattice
Steven R. Finch, Symmetric Random Walk on n-Dimensional Integer Lattice [Cached copy, with permission of the author]
N. J. A. Sloane, Transforms

Invert A002896, A094059.

Column k=3 of A361397.

read transforms; t1 := [ seq(A002896(i),i=1..25) ]; INVERTi(t1);
# second Maple program:
b:= proc(n) option remember; `if`(n<2, 5*n+1,
      (2*(2*n-1)*(10*n^2-10*n+3) *b(n-1)
       -36*(n-1)*(2*n-1)*(2*n-3) *b(n-2)) /n^3)
    end:
g:= proc(n) g(n):= `if` (n<1, -1, -add(g(n-i) *b(i), i=1..n)) end:
a:= n-> abs(g(n)):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 02 2012

(* A002896 : *) b[n_] := b[n] = Binomial[2*n, n]*HypergeometricPFQ[{1/2, -n, -n}, {1, 1}, 4]; max = 32; a[0] = 1; se = Series[ Sum[ a[n] x^(2 n), {n, 1, max}] - 1 + 1/Sum[ b[n]*x^(2 n), {n, 0, max}], {x, 0, max}]; coes = CoefficientList[se, x]; sol = First[ Solve[ Thread[ coes == 0]]]; Table[ a[n], {n, 0, 16}] /. sol (* Jean-François Alcover, Dec 20 2011 *)
b[n_] := b[n] = If[n < 2, 5*n + 1, (2*(2*n - 1)*(10*n^2 - 10*n + 3)*b[n-1] - 36*(n - 1)*(2*n - 1)*(2*n - 3)*b[n-2]) / n^3];
g[n_] := g[n] = If[n < 1, -1, -Sum [g[n - i]*b[i], {i, 1, n}]];
a[n_] := Abs[g[n]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jan 12 2018, after Alois P. Heinz *)

Define a_0, a_1, ... = [ 1, 6, 54, ... ] by 1+Sum b_i x^i = 1/(1-Sum a_i x^i) where b_0, b_1, ... = [ 1, 6, 90, ... ] = A002896.
Or, Sum[ a(n) x^(2n), n=1, 2, ...infinity ] = 1-1/Sum[ A002896(n)*x^(2n), n=0, 1, ...infinity ].
G.f.: 2-sqrt(1+12*z) /hypergeom([1/8, 3/8], [1], 64/81*z *(1+sqrt(1-36*z))^2 *(2+sqrt(1-36*z))^4 /(1+12*z)^4)/ hypergeom([1/8, 3/8], [1], 64/81*z *(1-sqrt(1-36*z))^2 *(2-sqrt(1-36*z))^4 /(1+12*z)^4). - Sergey Perepechko, Jan 30 2011
a(n) ~ c * 36^n / n^(3/2), where c = 0.1014559485279103938501072426734... . - Vaclav Kotesovec, Sep 13 2014
c = 384 * (3 + 2*sqrt(3)) * Pi^(9/2) / (Gamma(1/24)^4 * Gamma(11/24)^4). - Vaclav Kotesovec, Apr 23 2023

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

Original entry on oeis.org

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

Offset: 0

Shel Kaphan, Mar 08 2023

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.

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.

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.

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}]]

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

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.

A361297 Number of n-dimensional cubic lattice walks with 2n steps from origin to origin and avoiding early returns to the origin.

Original entry on oeis.org

1, 2, 20, 996, 108136, 19784060, 5389230384, 2031493901304, 1009373201680848, 638377781979995244, 500510427096797296240, 476433596774288713285352, 541348750963243079098368768, 723928411313545718524263072248, 1125748074023593276830674831519936

Offset: 0

Alois P. Heinz, Mar 08 2023

a(n) is a multiple of 2n for n>=1.

Alois P. Heinz, Table of n, a(n) for n = 0..212

Main diagonal of A361397.

Cf. A005843, A303503.

b:= proc(n, l) option remember; add(add((h-> `if`(n<=
      add(v, v=h), 0, `if`(n=1, 1, `if`(h[-1]=0, 0,
        b(n-1, h)))))(sort(subsop(i=abs(l[i]+j), l))),
          j=[-1, 1]), i=1..nops(l))
    end:
a:= n-> `if`(n=0, 1, b(2*n, [0$n])):
seq(a(n), n=0..15);
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0 or i=1, 1,
      add(b(n-j, i-1)*binomial(n, j)^2, j=0..n))
    end:
g:= proc(n, k) option remember; `if` (n<1, -1,
      -add(g(n-i, k)*(2*i)!*b(i, k)/i!^2, i=1..n))
    end:
a:= n-> abs(g(n$2)):
seq(a(n), n=0..15);

b[n_, i_] := b[n, i] = If[n == 0 || i == 1, 1, Sum[b[n - j, i - 1]*Binomial[n, j]^2, {j, 0, n}]];
g[n_, k_] := g[n, k] = If [n < 1, -1, -Sum[g[n - i, k]*(2i)!* b[i, k]/i!^2, {i, 1, n}]];
a[n_] := Abs[g[n, n]];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, May 27 2023, from 2nd Maple program *)

a(n) = A361397(n,n).
From Vaclav Kotesovec, Apr 23 2023: (Start)
a(n) ~ c * d^n * n^(2*n), where d = 1.138128465642... and c = 1.72802011936...
a(n) ~ A303503(n). (End)

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

Original entry on oeis.org

1, 10, 170, 6500, 332050, 19784060, 1296395700, 90616189800, 6637652225250, 503852804991500, 39337349077483420, 3142010167321271000, 255747325678297576100, 21150729618673827139000, 1773152567858996728205000, 150409554094012703302602000, 12890454660664800562838261250

Offset: 0

Shel Kaphan, Mar 09 2023

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 5-d case is the series corresponding to A287317.
To satisfy this g.f. equation, a(0) should be 0, but we give it as 1 since there is one trivial loop of 0 steps, and for consistency with related sequences.
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) = 100^n.

Alois P. Heinz, Table of n, a(n) for n = 0..503
Jonathan Novak, Pólya's Random Walk Theorem.

Cf. A287317, A039699 (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..4 dimensions: |A002420|, A054474, A049037, A359801.
Column k=5 of A361397.
Cf. A169714.

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

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

INVERTi transform of A169714.

cp's OEIS Frontend

A054474 Number of walks on square lattice that start and end at origin after 2n steps, not touching origin at intermediate stages.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A139271 a(n) = 2*n*(4*n-3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A361297 Number of n-dimensional cubic lattice walks with 2n steps from origin to origin and avoiding early returns to the origin.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A139271 a(n) = 2n(4*n-3).