A002896 -id:A002896 - cp's OEIS frontend

A010567 Number of 2n-step self-avoiding closed paths (or cycles) on the 3-dimensional cubic lattice.

6, 24, 264, 3312, 48240, 762096, 12673920, 218904768, 3891176352, 70742410800, 1309643747808, 24609869536800, 468270744898944, 9005391024862848, 174776445357365040, 3419171337633496704

Offset: 1

N. J. A. Sloane

This sequence agrees with A001413 except for n=1, for which the given value is "purely conventional" (although the convention is non-standard): it counts 6 two-step closed paths, all of which visit no node twice but use an edge twice, so whether they are "self-avoiding" is indeed a matter of agreement. Same considerations apply to the first terms of A010568-A010570. - Andrey Zabolotskiy, May 29 2018

M. E. Fisher and D. S. Gaunt, Ising model and self-avoiding walks on hypercubical lattices and high density expansions, Phys. Rev. 133 (1964) A224-A239.

Essentially the same as A001413.

Cf. A010568 (analog in 4 dimensions), A010569 (in 5D), A010570 (in 6D), A130706 (in 1D), A010566 (in 2D, different convention for n=1), A002896 (closed walks, not necessarily self-avoiding), A001412 (self-avoiding walks, not necessarily closed), A039618, A038515.

def A010567(n): # For illustration - becomes slow for n > 5
    if not hasattr(A:=A010567, 'terms'):
        A.terms=[6]; O=0,; A.paths=[(O*3, (1,)+O*2, t+O)for t in((2,0),(1,1))]
    while n > len(A.terms):
        for L in (0,1):
            new = []; cycles = 0
            for path in A.paths:
                end = path[-1]
                for i in (0,1,2):
                   for s in (1,-1):
                      t = tuple(end[j]if j!=i else end[j]+s for j in (0,1,2))
                      if t not in path: new.append(path+(t,))
                      elif L and t==path[0]: cycles += 24 if path[2][1] else 6
            A.paths = new
        A.terms.append(cycles)
    return A.terms[n-1] # M. F. Hasler, Jun 17 2025

a(8)-a(10) copied from A001413 by Andrey Zabolotskiy, May 29 2018
a(11)-a(12) copied from A001413 by Pontus von Brömssen, Feb 28 2024
a(13)-a(16) (using A001413) from Alois P. Heinz, Feb 28 2024
Name edited and "self-avoiding" added by M. F. Hasler, Jun 17 2025

A135394 Number of walks of length 2n+2 from origin to (1,1,0) on a cubic lattice.

Original entry on oeis.org

2, 48, 1200, 31920, 890820, 25768512, 766053288, 23265871200, 718834982580, 22523567008800, 714044153702880, 22861678250567520, 738191825153055000, 24011251877148076800, 786038700362427057600, 25877760367136497398720

Offset: 0

Stefan Hollos (stefan(AT)exstrom.com), Dec 11 2007

a(n) is the number of walks of length 2n+2 on a cubic lattice that begin at the origin and end at (1,1,0) using steps (1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1).

G. C. Greubel, Table of n, a(n) for n = 0..100
S. Hollos and R. Hollos, Lattice Paths and Walks.

Cf. A002896.

Table[Binomial[2*n + 2, n]*Sum[Binomial[n, k]*Binomial[n + 2, k + 1]*Binomial[2*k + 1, k], {k, 0, n}], {n, 0, 25}] (* G. C. Greubel, Oct 12 2016 *)

a(n) = binomial(2n+2,n) * sum( binomial(n,k) * binomial(n+2,k+1) * binomial(2k+1,k), k, 0, n )

a(n) = binomial(2*n+2,n) * sum(k=0,n, binomial(n,k) * binomial(n+2,k+1) * binomial(2*k+1,k)) \\ Charles R Greathouse IV, Oct 12 2016

a(n) = binomial(2n+2,n) * Sum_{k=0..n} ( binomial(n,k) * binomial(n+2,k+1) * binomial(2k+1,k) ).
6*(n+2)^2*a(n) = (n+1)*((7*n+11)*A002896(n+1)-18*(2*n+1)*A002896(n)). - Sergey Perepechko, Feb 08 2011
G.f.: (1/(12*x))*(-2*(4*x-1)*(36*x-1)*x*g'' + (-720*x^2+160*x-3)*g' + (-144*x+18)*g) where g is the o.g.f. of A002896. - Mark van Hoeij, Nov 12 2011
a(n) ~ 3^(7/2) * 36^n / (Pi^(3/2) * n^(3/2)). - Vaclav Kotesovec, Nov 27 2017

A303503 a(n) = (2n)! [x^(2n)] BesselI(0,2x)^n.

Original entry on oeis.org

1, 2, 36, 1860, 190120, 32232060, 8175770064, 2898980908824, 1369263687414480, 830988068906518380, 630109741730668410640, 583773362067938664133512, 648851848280206013365243776, 852146184628067383511375555000, 1305460597778526044143501996708800, 2307324514460203126471248458864413200

Offset: 0

Ilya Gutkovskiy, Apr 25 2018

nonn

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

Main diagonal of A287318.

Cf. A000984, A002894, A002896, A033935, A039699, A287317, A361297.

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:
a:= n-> (2*n)!*b(n$2)/n!^2:
seq(a(n), n=0..17);  # Alois P. Heinz, Jan 29 2023

Table[(2 n)! SeriesCoefficient[BesselI[0, 2 x]^n, {x, 0, 2 n}], {n, 0, 15}]

a(n) = A287318(n,n).
a(n) ~ c * d^n * n^(2*n), where c = 1.72802011936236389522137050964080... and d = 1.1381284656425793765251319541847869000364101065484286935... - Vaclav Kotesovec, Apr 26 2018
a(n) = A000984(n)*A033935(n). - Alois P. Heinz, Jan 30 2023

A307468 Cogrowth sequence for the Heisenberg group.

Original entry on oeis.org

1, 4, 28, 232, 2156, 21944, 240280, 2787320, 33820044, 424925872, 5486681368, 72398776344, 972270849512, 13247921422480, 182729003683352, 2546778437385032, 35816909974343308, 507700854900783784, 7246857513425470288, 104083322583897779656

Offset: 0

Igor Pak, Apr 09 2019

This is the number of words of length 2n in the letters x,x^{-1},y,y^{-1} that equal the identity of the Heisenberg group H=.

Also, this is the number of closed walks of length 2n on the square lattice enclosing algebraic area 0 [Béguin et al.]. - Andrey Zabolotskiy, Sep 15 2021

			For n=1 the a(1)=4 words are x^{-1}x, xx^{-1}, y^{-1}y, yy^{-1}.

Jay Pantone, Table of n, a(n) for n = 0..200
Cédric Béguin, Alain Valette and Andrzej Zuk, On the spectrum of a random walk on the discrete Heisenberg group and the norm of Harper's operator, Journal of Geometry and Physics, 21 (1997), 337-356.
D. Lind and K, Schmidt, A survey of algebraic actions of the discrete Heisenberg group, arXiv:1502.06243 [math.DS], 2015; Russian Mathematical Surveys, 70:4 (2015), 77-142.

Related cogrowth sequences: Z A000984, Z^2 A002894, Z^3 A002896, (Z/kZ)^*2 for k = 2..5: A126869, A047098, A107026, A304979, Richard Thompson's group F A246877. The cogrowth sequences for BS(N,N) for N = 2..10 are A229644, A229645, A229646, A229647, A229648, A229649, A229650, A229651, A229652.

Cf. A352838, A178106.

Asymptotics: a(n) ~ (1/2) * 16^n * n^(-2).

A328713 Constant term in the expansion of (1 + x + y + z + 1/x + 1/y + 1/z)^n.

Original entry on oeis.org

1, 1, 7, 19, 127, 511, 3301, 16297, 103279, 570367, 3595177, 21167917, 133789789, 818625133, 5207248879, 32649752779, 209258291599, 1333828204303, 8612806088761, 55546469634733, 361143420408337, 2349709451702737, 15370341546766939, 100695951740818903, 662213750028892429

Offset: 0

Seiichi Manyama, Oct 26 2019

nonn

a(n) is the number of n-step closed walks (from origin to origin) in cubic lattice where each step changes at most one component by -1 or by +1. - Alois P. Heinz, Oct 26 2019

			(1+x+y+z+1/x+1/y+1/z)^2 = x^2 + 1/x^2 + y^2 + 1/y^2 + z^2 + 1/z^2 + 2 * (xy + 1/(xy) + yz + 1/(yz) + zx + 1/(zx) + x/y + y/x + y/z + z/y + z/x + x/z + x + 1/x + y + 1/y + z + 1/z) + 7. So a(2) = 7.

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

Row 3 of A328718.

Cf. A002426, A002896, A201805.

{a(n) = polcoef(polcoef(polcoef((1+x+y+z+1/x+1/y+1/z)^n, 0), 0), 0)}

From Vaclav Kotesovec, Oct 26 2019: (Start)
Recurrence: n^3*a(n) = (2*n - 1)*(2*n^2 - 2*n + 1)*a(n-1) + (n-1)*(34*n^2 - 68*n + 41)*a(n-2) - 38*(n-2)*(n-1)*(2*n - 3)*a(n-3) - 105*(n-3)*(n-2)*(n-1)*a(n-4).
a(n) ~ 7^(n + 3/2) / (8 * Pi^(3/2) * n^(3/2)). (End)
E.g.f.: exp(x) * BesselI(0,2*x)^3. - Ilya Gutkovskiy, Oct 26 2019

A302181 Number of 3D walks of type abb.

Original entry on oeis.org

1, 5, 62, 1065, 21714, 492366, 12004740, 308559537, 8255788970, 227976044010, 6457854821340, 186814834574550, 5500292590186380, 164387681345290500, 4976887208815547640, 152378485941172462785, 4711642301137121933850, 146964278352052950118770, 4619875954522866283392300

Offset: 0

N. J. A. Sloane, Apr 09 2018

See Dershowitz (2017) for precise definition.

Nachum Dershowitz, Touchard's Drunkard, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.

Cf. A000108, A000984, A002212, A002896, A005572, A026375, A064037, A081671, A138547, A145847, A145867, A150500, A202814.

Cf. A005558, A126869.

C := n-> binomial(2*n, n)/(n+1): # Catalan numbers
A302181 := n-> add(binomial(2*n, k)*C(iquo(k+1, 2))*C(iquo(k, 2))*(2*iquo(k, 2)+1)*add((-1)^(k+j)*binomial(2*n-k, iquo(j,2)), j=0..2*n-k), k=0..2*n): seq(A302181(n), n = 0 .. 18); # Mélika Tebni, Nov 06 2024

a(n) = Sum_{k=0..2*n} binomial(2*n, k) * A005558(k) * A126869(2*n-k). - Mélika Tebni, Nov 06 2024

a(8)-a(18) from Nachum Dershowitz, Aug 03 2020

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

Original entry on oeis.org

1, 12, 396, 19920, 1281420, 96807312, 8175770064, 748315668672, 72729762868620, 7402621930738320, 781429888276676496, 84955810313787521472, 9463540456205136873936, 1075903653146632508721600, 124461755084172965028753600, 14615050011682746903615601920

Offset: 0

Dave R.M. Langers, Oct 12 2022

			a(1)=12, because twelve paths start at the origin, visit one of the adjacent vertices, and immediately return to the origin, resulting in 12 different paths of length 2n=2*1=2.

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

Row k=6 of A287318.

1-5 dimensional analogs are A000984, A002894, A002896, A039699, A287317.

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:
a:= n-> (2*n)!*b(n, 6)/n!^2:
seq(a(n), n=0..15);  # Alois P. Heinz, Jan 30 2023

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

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

A135395 Number of walks of length 2n+3 from origin to (1,1,1) on a cubic lattice.

Original entry on oeis.org

6, 180, 5040, 143640, 4199580, 125621496, 3830266440, 118655943120, 3724872182460, 118248726796200, 3789926661961440, 122473276342326000, 3986235855826497000, 130561182081992667600, 4300094066688571550400

Offset: 0

Stefan Hollos (stefan(AT)exstrom.com), Dec 11 2007

a(n) is the number of walks of length 2*n+3 in a cubic lattice that begin at the origin and end at (1,1,1) using steps (1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1).

G. C. Greubel, Table of n, a(n) for n = 0..250
S. Hollos and R. Hollos, Lattice Paths and Walks.

Cf. A002896.

sq := (1-40*x+144*x^2)^(1/2); pb := 54*x*(108*x^2-27*x+1+(9*x-1)*sq);
H1 := hypergeom([7/6,1/3],[1],pb); H2 := hypergeom([1/6,4/3],[1],pb);
fa := (10-72*x-6*sq)^(1/2)/(432*x^3);
ogf := fa*((648*x^2-162*x+(54*x+3)*sq+5)*H1^2 - (648*x^2-342*x+(54*x+6)*sq+10)*H1*H2 - (180*x-5-3*sq)*H2^2);
series(ogf,x=0,20) # Mark van Hoeij, Nov 12 2011

Table[Binomial[2n+3,n]Sum[Binomial[n,k]Binomial[n+3,k+2]Binomial[2k+2,k+1],{k,0,n}],{n,0,20}] (* Harvey P. Dale, Mar 20 2012 *)

a(n) = binomial(2n+3,n) * sum( binomial(n,k) * binomial(n+3,k+2) * binomial(2k+2,k+1), k, 0, n )

a(n) = binomial(2*n+3,n) * sum(k=0,n, binomial(n,k) * binomial(n+3,k+2) * binomial(2*k+2,k+1)) \\ Charles R Greathouse IV, Oct 12 2016

a(n) = binomial(2n+3,n) * Sum_{k=0..n} (binomial(n,k) * binomial(n+3,k+2) * binomial(2k+2,k+1)).
G.f.: ((12*(4*x-1)*(36*x-1)/x)*g'' + (12*(288*x^2-60*x+1)/x^2)*g' + (72*(6*x-1)/x^2)*g)/288 where g is the o.g.f. of A002896. - Mark van Hoeij, Nov 12 2011
From Vaclav Kotesovec, Nov 27 2017: (Start)
Recurrence: n*(n+2)*(n+3)*a(n) = 4*(2*n + 3)*(5*n^2 + 10*n + 3)*a(n-1) - 36*n*(2*n + 1)*(2*n + 3)*a(n-2).
a(n) ~ 2^(2*n + 1) * 3^(2*n + 9/2) / (Pi*n)^(3/2). (End)
a(n) = (2*n+1)*(2*n+3)*binomial(2*n,n)*((n+3)*A005802(n+1)-(n+1)*A005802(n)). - Mark van Hoeij, Nov 12 2023

A245067 Number of three-dimensional random walks with 2n steps in the wedge region x >= y >= z, beginning and ending at the origin without crossing the wedge boundary.

Original entry on oeis.org

1, 2, 12, 120, 1610, 25956, 474012, 9475752, 202921290, 4587734580, 108376022040, 2654745191280, 67043341981980, 1737717447946200, 46062204663294000, 1245096242017227360, 34239776369652506970, 956050033694583839220

Offset: 0

Jean-François Alcover, Nov 12 2014

			For 2n=4, the 12 acceptable walks are:
(0, 0, -1), (0, -1, -1), (0, 0, -1), (0 ,0, 0);
(0, 0, -1), (0, 0, 0), (0, 0, -1), (0 ,0, 0);
(0, 0, -1), (0, 0, 0), (1, 0, 0), (0 ,0, 0);
(0, 0, -1), (1, 0, -1), (0, 0, -1), (0 ,0, 0);
(0, 0, -1), (1, 0, -1), (1, 0, 0), (0 ,0, 0);
(1, 0, 0), (0, -1, -1), (0, 0, -1), (0 ,0, 0);
(1, 0, 0), (0, 0, 0), (0, 0, -1), (0 ,0, 0);
(1, 0, 0), (0, 0, 0), (1, 0, 0), (0 ,0, 0);
(1, 0, 0), (1, 0, -1), (0, 0, -1), (0 ,0, 0);
(1, 0, 0), (1, 0, -1), (1, 0, 0), (0 ,0, 0);
(1, 0, 0), (1, 1, 0), (0, 0, -1), (0 ,0, 0);
(1, 0, 0), (1, 1, 0), (1, 0, 0), (0 ,0, 0).

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.9 Polya's random walk constants, p. 326.

Eric Weisstein's MathWorld, Polya's Random Walk Constants

Cf. A000108, A002896, A086230, A086231.

a[n_] := CatalanNumber[n]*HypergeometricPFQ[{1/2, -n-1, -n}, {2, 2}, 4]; Table[a[n], {n, 0, 20}]

a(n) = sum_{k=0..n} (2n)!*(2k)!/((n-k)!*(n+1-k)!*k!^2*(k+1)!^2).
a(n) = C(n) * 3F2(1/2, -n-1, -n; 2, 2; 4) where C(n) is the n-th Catalan number and 3F2 the hypergeometric function.
a(n) ~ 2^(2*n-4) * 3^(2*n+9/2) / (Pi^(3/2) * n^(9/2)). - Vaclav Kotesovec, Nov 13 2014
Recurrence: n*(n+2)^2*a(n) = 2*(2*n-1)*(10*n^2 + 2*n - 3)*a(n-1) - 36*(n-1)*(2*n-3)*(2*n-1)*a(n-2). - Vaclav Kotesovec, May 14 2016

A302180 Number of 3D walks of type aad.

Original entry on oeis.org

1, 1, 3, 7, 23, 71, 251, 883, 3305, 12505, 48895, 193755, 783355, 3205931, 13302329, 55764413, 236174933, 1008773269, 4343533967, 18834033443, 82201462251, 360883031291, 1592993944723, 7066748314147, 31493800133173, 140953938878821, 633354801073571, 2856369029213263

Offset: 0

N. J. A. Sloane, Apr 09 2018

See Dershowitz (2017) for precise definition.
Number of 3D walks of length n in the first octant using steps (1, 1, 0), (1, -1, 0), (1, 0, 1), (1, 0, -1) and (1, 0, 0) that start at the origin and end at (n, 0, 0). The analogous problem in 2D is given by the Motzkin numbers A001006. - Farzan Byramji, Mar 06 2021
Inverse binomial transform of A145867 (Number of 3D walks of type aae). - Mélika Tebni, Nov 05 2024

Nachum Dershowitz, Touchard's Drunkard, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.

Cf. A000108, A000984, A001006, A002212, A002896, A005572, A026375, A064037, A081671, A138547, A145847, A145867, A150500, A202814.

M := n-> add(binomial(n, 2*k)*binomial(2*k, k)/(k+1), k = 0 .. iquo(n,2)): # Motzkin numbers
A302180 := n-> add((-1)^(n-k)*binomial(n, k)*add(binomial(k, j)*M(j)*M(k-j), j=0..k), k=0..n):  seq(A302180(n), n = 0 .. 26); # Mélika Tebni, Nov 05 2024

a(14)-a(26) from Farzan Byramji, Mar 06 2021

cp's OEIS Frontend

A010567 Number of 2n-step self-avoiding closed paths (or cycles) on the 3-dimensional cubic lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Extensions

A135394 Number of walks of length 2n+2 from origin to (1,1,0) on a cubic lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

A303503 a(n) = (2*n)! * [x^(2*n)] BesselI(0,2*x)^n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A307468 Cogrowth sequence for the Heisenberg group.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A328713 Constant term in the expansion of (1 + x + y + z + 1/x + 1/y + 1/z)^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A302181 Number of 3D walks of type abb.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A135395 Number of walks of length 2n+3 from origin to (1,1,1) on a cubic lattice.

Views

Author

Keywords

Comments

Links

A303503 a(n) = (2n)! [x^(2n)] BesselI(0,2x)^n.