0,2

The discrete space in which the walking happens is a triangular prism infinite in both directions along the x-axis. One vertex is the root, the origin. The basis is the set of single-step vectors, which we abbreviate as l (left), r (right), c (one step "clockwise" around the triangle) and c- (one step counterclockwise, more properly denoted c^-1). Self-avoidance eliminates those random walks corresponding to words isomorphic to those quarternary numbers beginning or containing lr, rl, cc-, or c-c, as these each return to a vertex visited a step before. Also eliminated are walks which return to a previously visited point by going around the triangle, as with c^3 = ccc and c^-3 = c-c-c-. Also eliminated are walks which return to a previously visited point by going in a square, as with lcrc-, lc-rc, crc-l, clc-r, rclc-, rc-lc. We are enumerating special subsets of the group C_3 X Z. Obviously a(n+1) < 3*a(n), but how much less depends on more and more complica ted geometrical (or grammatical) constraints. The shortest trapping walks are of length 7, to which none of the four basis vectors can be legally appended. This sequence will be extended shortly based on my 16-year-old son's software, allowing asymptotic estimates.

No closed-form solution known, or likely.

a(0) = 1, as there is one self-avoiding walk of length 0, namely the null-walk the walk whose steps are the null set).

a(1) = 4 because (using the terminology in the Comment), the 4 possible 1-step walks are W_1 = {l,r,c,c-}.

a(2) = 12 because the set of legal 2-step walks are {l^2, lc, lc-, r^2, rc, rc-, c^2, cl, cr, c^-2, c0-l, c-r}.

a(3) = 34 because we have every W_2 concatenated with {l,r,c,c-} except for those with immediate violations (lr etc.) and those two which go in a triangle {c^3, c^-3}; hence a(3) = 3*a(2) - 2 = 3*12 - 2 = 36 - 2 = 34. a(4) = 92 because W_4 = {W_3 concatenated with W_1} - {immediate violations} - {squares} - {W_1 concatenated with a triangle} = 3*34 - the number of walks which self-intersect first on the 4th step = 102 - |{lcrc-, lc-rc, crc-l, clc-r, rclc-, rc-lc}| - |{lc^3, lc^-3, rc^3, rc^-3}| = 102 - 6 - 4 = 92.

Cf. A002902, A002903, A077817.

Sequence in context: A036880 A110335 A166294 this_sequence A079818 A115390 A005056

Adjacent sequences: A107066 A107067 A107068 this_sequence A107070 A107071 A107072

nonn

Jonathan Vos Post (jvospost3(AT)gmail.com), May 10 2005