A366058 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.

1, 6, 30, 126, 462, 1566, 5070, 15966, 49422, 151326, 460110, 1392606, 4202382, 12656286, 38067150, 114398046, 343587342, 1031548446, 3096218190, 9291800286, 27881692302, 83657659806, 250998145230, 753044767326, 2259234965262, 6777906222366, 20334121320270, 61003169267166, 183011118414222

Offset: 0

Author

Scott R. Shannon, Dec 15 2023

Keywords

• nonn

Comments

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

Examples

			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.
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.
		

Crossrefs

Cf. A173033 (2D square lattice), A001412.

Cf. A371064.

Formula

Conjectured: a(n) = 6*(4*3^(n-1) - 4*2^(n-1) + 1), for n > 0.

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