A049037 -id:A049037 - cp's OEIS frontend

A002896 Number of 2n-step polygons on cubic lattice.

1, 6, 90, 1860, 44730, 1172556, 32496156, 936369720, 27770358330, 842090474940, 25989269017140, 813689707488840, 25780447171287900, 825043888527957000, 26630804377937061000, 865978374333905289360, 28342398385058078078010, 932905175625150142902300

Offset: 0

N. J. A. Sloane

Number of walks with 2n steps on the cubic lattice Z^3 beginning and ending at (0,0,0).
If A is a random matrix in USp(6) (6 X 6 complex matrices that are unitary and symplectic) then a(n) is the 2n-th moment of tr(A^k) for all k >= 7. - Andrew V. Sutherland, Mar 24 2008
Diagonal of the rational function R(x,y,z,w) = 1/(1 - (w*x*y + w*x*z + w*y + x*z + y + z)). - Gheorghe Coserea, Jul 14 2016
Constant term in the expansion of (x + 1/x + y + 1/y + z + 1/z)^(2n). - Harry Richman, Apr 29 2020

			1 + 6*x + 90*x^2 + 1860*x^3 + 44730*x^4 + 1172556*x^5 + 32496156*x^6 + ...

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..645
David H. Bailey, Jonathan M. Borwein, David Broadhurst and M. L. Glasser, Elliptic integral evaluations of Bessel moments, arXiv:0801.0891 [hep-th], 2008.
Nikolai Beluhov, Powers of 2 in Balanced Grid Colourings, arXiv:2504.21451 [math.CO], 2025.
C. Domb, On the theory of cooperative phenomena in crystals, Advances in Phys., 9 (1960), 149-361.
Nachum Dershowitz, Touchard's Drunkard, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.
Robert Dougherty-Bliss, Christoph Koutschan, Natalya Ter-Saakov, and Doron Zeilberger, The (Symbolic and Numeric) Computational Challenges of Counting 0-1 Balanced Matrices, arXiv:2410.07435 [math.CO], 2024. See p. 5.
Li Gan, On the algebraic area of cubic lattice walks, arXiv:2307.08732 [math-ph], 2023.
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 p. 23.
W. K. Hayman, A Generalisation of Stirling's Formula, Journal für die reine und angewandte Mathematik, (1956), vol. 196, pp. 67-95.
John A. Hendrickson, Jr., On the enumeration of rectangular (0,1)-matrices, Journal of Statistical Computation and Simulation, 51 (1995), 291-313.
Heng Huat Chan, Yoshio Tanigawa, Yifan Yang, and Wadim Zudilin, New analogues of Clausen's identities arising from the theory of modular forms, Advances in Mathematics, 228:2 (2011), pp. 1294-1314; doi:10.1016/j.aim.2011.06.011.
G. S. Joyce, The simple cubic lattice Green function, Phil. Trans. Roy. Soc., 273 (1972), 583-610.
Kiran S. Kedlaya and Andrew V. Sutherland, Hyperelliptic curves, L-polynomials and random matrices, arXiv:0803.4462 [math.NT], 2008-2010.
Yen Lee Loh, A general method for calculating lattice Green functions on the branch cut, arXiv:1706.03083 [math-ph], 2017.
Nobu C. Shirai and Naoyuki Sakumichi, Universal Negative Energetic Elasticity in Polymer Chains: Crossovers among Random, Self-Avoiding, and Neighbor-Avoiding Walks, arXiv:2408.14992 [cond-mat.soft], 2024. See p. 5.
Chunwei Song and Bowen Yao, On Combinatorial Rectangles with Minimum oo-Discrepancy, arXiv:1909.05648 [math.CO], 2019. See p. 7 for another interpretation.
Ralph A. Raimi and Jet Wimp, Review of book "A=B" by M. Petkovsek et al., Mathematical Intelligencer, 23 (No. 4, 2001), pp. 72-77.

C(2n, n) times A002893.
Cf. A049020, A049037, A084261, A138540, A174516.
Related to diagonal of rational functions: A268545-A268555.
Row k=3 of A287318.

a := proc(n) local k; binomial(2*n,n)*add(binomial(n,k)^2 *binomial(2*k,k), k=0..n); end;
# second Maple program
a:= proc(n) option remember; `if`(n<2, 5*n+1,
      (2*(2*n-1)*(10*n^2-10*n+3) *a(n-1)
       -36*(n-1)*(2*n-1)*(2*n-3) *a(n-2)) /n^3)
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Nov 02 2012
A002896 := n -> binomial(2*n,n)*hypergeom([1/2, -n, -n], [1, 1], 4):
seq(simplify(A002896(n)), n=0..16); # Peter Luschny, May 23 2017

Table[Binomial[2n,n] Sum[Binomial[n,k]^2 Binomial[2k,k],{k,0,n}],{n,0,20}] (* Harvey P. Dale, Jan 24 2012 *)
a[ n_] := If[ n < 0, 0, HypergeometricPFQ[ {-n, -n, 1/2}, {1, 1}, 4] Binomial[ 2 n, n]] (* Michael Somos, May 21 2013 *)

a(n)=binomial(2*n,n)*sum(k=0,n,binomial(n, k)^2*binomial(2*k, k)) \\ Charles R Greathouse IV, Oct 31 2011

def A002896():
    x, y, n = 1, 6, 1
    while True:
        yield x
        n += 1
        x, y = y, ((4*n-2)*((10*(n-1)*n+3)*y-18*(n-1)*(2*n-3)*x))//n^3
a = A002896()
[next(a) for i in range(17)]  # Peter Luschny, Oct 09 2013

a(n) = C(2*n, n)*Sum_{k=0..n} C(n, k)^2*C(2*k, k).
a(n) = (4^n*p(1/2, n)/n!)*hypergeom([-n, -n, 1/2], [1, 1], 4), where p(a, k) = Product_{i=0..k-1} (a+i).
E.g.f.: Sum_{n>=0} a(n)*x^(2*n)/(2*n)! = BesselI(0, 2*x)^3. - Corrected by Christopher J. Smyth, Oct 29 2012
D-finite with recurrence: n^3*a(n) = 2*(2*n-1)*(10*n^2-10*n+3)*a(n-1) - 36*(n-1)*(2*n-1)*(2*n-3)*a(n-2). - Vladeta Jovovic, Jul 16 2004
An asymptotic formula follows immediately from an observation of Bruce Richmond and me in SIAM Review - 31 (1989, 122-125). We use Hayman's method to find the asymptotic behavior of the sum of squares of the multinomial coefficients multi(n, k_1, k_2, ..., k_m) with m fixed. From this one gets a_n ~ (3/4)*sqrt(3)*6^(2*n)/(Pi*n)^(3/2). - Cecil C Rousseau (ccrousse(AT)memphis.edu), Mar 14 2006
G.f.: (1/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 26 2011
a(n) = binomial(2*n,n)*A002893(n). - Mark van Hoeij, Oct 29 2011
G.f.: (1/2)*(10-72*x-6*(144*x^2-40*x+1)^(1/2))^(1/2)*hypergeom([1/6, 1/3],[1],54*x*(108*x^2-27*x+1+(9*x-1)*(144*x^2-40*x+1)^(1/2)))^2. - Mark van Hoeij, Nov 12 2011
PSUM transform is A174516. - Michael Somos, May 21 2013
0 = (-x^2+40*x^3-144*x^4)*y''' + (-3*x+180*x^2-864*x^3)*y'' + (-1+132*x-972*x^2)*y' + (6-108*x)*y, where y is the g.f. - Gheorghe Coserea, Jul 14 2016
a(n) = [(x y z)^0] (x + 1/x + y + 1/y + z + 1/z)^(2*n). - Christopher J. Smyth, Sep 25 2018
a(n) = (1/Pi)^3*Integral_{0 <= x, y, z <= Pi} (2*cos(x) + 2*cos(y) + 2*cos(z))^(2*n) dx dy dz. - Peter Bala, Feb 10 2022
a(n) = Sum_{i+j+k=n, 0<=i,j,k<=n} multinomial(2n [i,i,j,j,k,k]). - Shel Kaphan, Jan 16 2023
Sum_{k>=0} a(k)/36^k = A086231 = (sqrt(3)-1) * (Gamma(1/24) * Gamma(11/24))^2 / (32*Pi^3). - Vaclav Kotesovec, Apr 23 2023
G.f.: HeunG(1/9,1/12,1/4,3/4,1,1/2,4*x)^2 (see Hassani et al.). - Stefano Spezia, Feb 16 2025

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

Original entry on oeis.org

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

A361397 Number A(n,k) of k-dimensional cubic lattice walks with 2n steps from origin to origin and avoiding early returns to the origin; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 2, 0, 1, 4, 2, 0, 1, 6, 20, 4, 0, 1, 8, 54, 176, 10, 0, 1, 10, 104, 996, 1876, 28, 0, 1, 12, 170, 2944, 22734, 22064, 84, 0, 1, 14, 252, 6500, 108136, 577692, 275568, 264, 0, 1, 16, 350, 12144, 332050, 4525888, 15680628, 3584064, 858, 0

Offset: 0

Alois P. Heinz, Mar 10 2023

Column k is INVERTi transform of k-th row of A287318.

			Square array A(n,k) begins:
  1,  1,     1,      1,       1,        1,        1, ...
  0,  2,     4,      6,       8,       10,       12, ...
  0,  2,    20,     54,     104,      170,      252, ...
  0,  4,   176,    996,    2944,     6500,    12144, ...
  0, 10,  1876,  22734,  108136,   332050,   796860, ...
  0, 28, 22064, 577692, 4525888, 19784060, 62039088, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns k=0-5 give: A000007, |A002420|, A054474, A049037, A359801, A361364.
Rows n=0-2 give: A000012, A005843, A139271.
Main diagonal gives A361297.
Cf. A000108, A287318.

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,k)-> `if`(n=0, 1, `if`(k=0, 0, g(n, k))):
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[n_, 0] = 0; b[n_, 1] = 1; b[0, k_] = 1;
b[n_, k_] := b[n, k] = Sum[Binomial[n, i]^2*b[i, k - 1], {i, 0, n}]; (* A287316 *)
g[n_, k_] := g[n, k] = b[n, k]*Binomial[2 n, n]; (* A287318 *)
a[n_, k_] := a[n, k] = g[n, k] - Sum[a[i, k]*g[n - i, k], {i, 1, n - 1}];
TableForm[Table[a[n, k], {k, 0, 10}, {n, 0, 10}]] (* Shel Kaphan, Mar 14 2023 *)

A(n,1)/2 = A000108(n-1) for n >= 1.

G.f. of column k: 2 - 1/Integral_{t=0..oo} exp(-t)*BesselI(0,2*t*sqrt(x))^k dt. - Shel Kaphan, Mar 19 2023

A094059 Analog of A054474 for walks on a 3-dimensional grid.

Original entry on oeis.org

1, 8, 152, 5056, 205720, 9305152, 449404224, 22695553536, 1183891745688, 63293536425280, 3449750940624064, 190972642327080448, 10708174630547469632, 606900724292865506816, 34711902088494315507200, 2000990161185766676951040, 116137589109102380308573080

Offset: 0

Matthijs Coster, Apr 29 2004

nonn

a(n) is the number of lattice paths on the 3 dimensional grid (using steps(1,1,1),(1,1,-1),(1,-1,1),(1,-1,-1),(-1,1,1),(-1,1,-1),(-1,-1,1)(-1,-1,-1)) that start and end at the origin after 2n steps, not touching the origin at intermediate stages. - Geoffrey Critzer, Feb 05 2012

Alois P. Heinz, Table of n, a(n) for n = 0..200
P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 90.

Cf. A049037.

series(2-1/hypergeom([1/4, 1/4],[1],64*x)^2, x=0, 20);  # Mark van Hoeij, Apr 16 2013

nn=40; a=Sum[Binomial[2n,n]^3 z^(2n), {n,0,nn}]; Select[CoefficientList[Series[2-1/a, {z,0,nn}], z], #>0&] (* Geoffrey Critzer, Feb 05 2012 *)

G.f.: 2-1/G(x) where G(x) = Sum_{n>=0} C(2n,n)^3 x^(2n). - Geoffrey Critzer, Feb 05 2012

a(n) ~ c * 64^n / n^(3/2), where c = 16*Pi^(9/2) / Gamma(1/4)^8 = 0.09252216985965964001991419323555310924034459466... . - Vaclav Kotesovec, Sep 05 2014, updated Mar 17 2024

a(6)-a(15) added by Geoffrey Critzer, Feb 05 2012

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.

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

A002896 Number of 2n-step polygons on cubic lattice.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

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

A361397 Number A(n,k) of k-dimensional cubic lattice walks with 2n steps from origin to origin and avoiding early returns to the origin; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A094059 Analog of A054474 for walks on a 3-dimensional grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

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

A174516 Partial sums of A002896.

Views

Author

Keywords

Examples