%I #60 Mar 13 2024 15:37:23
%S 1,6,30,126,462,1566,5070,15966,49422,151326,460110,1392606,4202382,
%T 12656286,38067150,114398046,343587342,1031548446,3096218190,
%U 9291800286,27881692302,83657659806,250998145230,753044767326,2259234965262,6777906222366,20334121320270,61003169267166,183011118414222
%N Number of n-step self-avoiding walks on a 3D cubic lattice where no step is to a lattice point closer to the origin than the current point.
%C Consider the n-step self-avoiding walks from the origin in the first octant that increase in L1 distance from the origin on each step. There are 3^n such walks since each of the n steps may occur in any of 3 ways. To account for all combinations of signs of coordinates, there are binomial(3,3)*2^3 = 8 octants so there would be 8*3^n n-step paths total, but they overlap where one or more coordinates of the endpoint are 0. They overlap pairwise on the binomial(3,2)*2^2 = 12 edges of the octahedron at distance n from the origin. Each edge represents 2^n paths, since holding one coordinate 0, either of the other two coordinates may be chosen for each step. So now we have 8*3^n - 12*2^n to avoid double counting the edges. However, since the edges overlap at each of the binomial(3,1)*2^1 = 6 octahedral vertices, we have now eliminated the vertices, so they must be added back in. There is only one n-step path from the origin to each octahedral vertex. Thus, there are 8*3^n - 12*2^n + 6 paths of length n that increase in distance from the origin at each step. - _Shel Kaphan_, Mar 10 2024
%F Conjectured: a(n) = 6*(4*3^(n-1) - 4*2^(n-1) + 1), for n > 0.
%F a(n) = Sum_{i=1..d} (-1)^(d-i) * binomial(d,i) * 2^i * i^n, where d=3, n>=1, which simplifies to 8*3^n - 12*2^n + 6, equivalent to conjectured formula (and row 3 of A371064). - _Shel Kaphan_, Mar 09 2024
%e a(2) = 30 as after two steps no walk can step closer to the origin than its current point, so a(2) = A001412(2) = 30.
%e a(3) = 126. Given the first two steps of the 3-step walk are to points (1,0,0) and (1,0,1) then a step to (0,0,1) is forbidden. This walk can be taken in 4*6 = 24 ways on the cubic lattice, so the total number of permitted walks is a(3) = A001412(3) - 24 = 150 - 24 = 126.
%Y Cf. A173033 (2D square lattice), A001412.
%Y Cf. A371064.
%K nonn
%O 0,2
%A _Scott R. Shannon_, Dec 15 2023