A394340 Number of self-avoiding walks on the cubic lattice with the first three orthogonal steps specified (see Comments).

1, 2, 6, 22, 92, 402, 1832, 8453, 39640, 186296, 881147, 4162866, 19721230, 93250730, 441549914, 2086950250, 9872284420, 46627034590, 220354970198, 1040000436047, 4910777435839, 23162527440081, 109292500313185, 515214985932766

Offset

1,2

Comments

The first step is in the +x direction, the first orthogonal step is in the +y direction, and the first step orthogonal to both x and y is in the +z direction.

Any walk on a cubic lattice (A001412) can be rotated and reflected such that these properties are satisfied. This provably represents an approximate 48-fold reduction in number (useful for exhaustively computing properties of the walks) and is analogous to A046171 on the square lattice.

Links

Table of n, a(n) for n=1..24.

Formula

a(n) = (A001412(n) + 24*A046171(n) + 18) / 48.

Example

There are 30 SAWs of length 2 (6 straight and 24 bent), but they can all be rotated such that the first step is in the +x direction, reducing the count to 5. Of these 5, one is straight and four are bent. The four bent walks can all be rotated such that their second step is in the +y direction, leaving the count at 2.

Prog

(Python)
import numpy as np
from copy import copy
nmax=10
count=[1, 2]
allwalks=[]
lap=lambda f, *l: list(map(f, *l))
allwalks.append(np.array([1, 0, 0]))
allwalks.append(np.array([[[1, 0, 0], [1, 1, 0]], [[1, 0, 0], [2, 0, 0]]]))
for n in range(2, nmax):
    template=allwalks[n-1]
    counter=0
    walks=[]
    for t in template:
        prewalk=np.array(t, dtype=int)
        ytrig=np.max(prewalk[:, 1])>0
        ztrig=np.max(prewalk[:, 2])>0
        grid=np.zeros([2*nmax+2]*3)
        prewalk+=nmax+1
        grid[*3*[nmax+1]]=1
        for j in range(n):
            grid[prewalk[j, 0], prewalk[j, 1], prewalk[j, 2]]=1
        opts=[]
        ep=[prewalk[-1, 0], prewalk[-1, 1], prewalk[-1, 2]]
        for i in range(6):
            epp=copy(ep)
            epp[i//2]+=(-1)**i
            if grid[*epp]==0 and (i<3 or ytrig and (i<5 or ztrig)):
                opts.append(epp)
        for o in opts:
            counter+=1
            walk=np.zeros([n+1, 3])
            walk[0:-1, :]=prewalk-[nmax+1]*3
            walk[-1, :]=np.array(o)-[nmax+1]*3
            walks.append(walk)
    allwalks.append(walks)
    count.append(counter)
print(count)

Crossrefs

Cf. A046171, A001412, A078717.

Sequence in context: A279569 A155866 A150273 * A342292 A303923 A379329

Adjacent sequences: A394337 A394338 A394339 * A394341 A394342 A394343

Keyword

nonn,walk

Author

Alex Klotz, Mar 17 2026

Status

approved