This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A107069 Number of self-avoiding 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 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). LINKS FORMULA No closed-form solution known, or likely. EXAMPLE 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, c-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. PROG (Python) w = [[[(0, 0)]]] for n in range(1, 15):     nw = []     for walk in w[-1]:         (x, t) = walk[-1]         nss = [(x-1, t), (x+1, t), (x, (t+1)%3), (x, (t-1)%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 14 12:40 EST 2019. Contains 329114 sequences. (Running on oeis4.)