|
| |
|
|
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
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
