

A107069


Number of selfavoiding walks of length n on an infinite triangular prism starting at the origin.


0



1, 4, 12, 34, 90, 222, 542, 1302, 3058, 7186, 16714, 38670, 89358, 205710, 472906
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

The discrete space in which the walking happens is a triangular prism infinite in both directions along the xaxis. One vertex is the root, the origin. The basis is the set of singlestep 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).


LINKS

Table of n, a(n) for n=0..14.


FORMULA

No closedform solution known, or likely.


EXAMPLE

a(0) = 1, as there is one selfavoiding walk of length 0, namely the nullwalk the walk whose steps are the null set).
a(1) = 4 because (using the terminology in the Comment), the 4 possible 1step walks are W_1 = {l,r,c,c}.
a(2) = 12 because the set of legal 2step walks are {l^2, lc, lc, r^2, rc, rc, c^2, cl, cr, c^2, cl, cr}.
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.


PROG

(Python)
w = [[[(0, 0)]]]
for n in range(1, 15):
nw = []
for walk in w[1]:
(x, t) = walk[1]
nss = [(x1, t), (x+1, t), (x, (t+1)%3), (x, (t1)%3)]
for ns in nss:
if ns not in walk:
nw.append(walk[:] + [ns])
w.append(nw)
print([len(x) for x in w])
# Andrey Zabolotskiy, Sep 19 2019


CROSSREFS

Cf. A002902, A002903, A077817, A038577, A302408, A007825.
Sequence in context: A209818 A094893 A036880 * A191823 A110335 A166294
Adjacent sequences: A107066 A107067 A107068 * A107070 A107071 A107072


KEYWORD

nonn,walk,more


AUTHOR

Jonathan Vos Post, May 10 2005


EXTENSIONS

a(4) and a(5) corrected, a(6)a(14) added by Andrey Zabolotskiy, Sep 19 2019


STATUS

approved



