login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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

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.

License Agreements, Terms of Use, Privacy Policy. .

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