OFFSET
0,2
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
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
EXAMPLE
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
KEYWORD
nonn
AUTHOR
Scott R. Shannon, Dec 15 2023
STATUS
approved