cp's OEIS Frontend

A107069 Number of self-avoiding walks of length n on an infinite triangular prism starting at the origin.

%I A107069 #16 Dec 05 2023 01:39:35
%S A107069 1,4,12,34,90,222,542,1302,3058,7186,16714,38670,89358,205710,472906,
%T A107069 1086138,2491666,5713318,13094950,30003190,68731010,157423986,
%U A107069 360530346,825626942,1890615518,4329196974,9912914314,22698017834,51972012258,119000208806
%N A107069 Number of self-avoiding walks of length n on an infinite triangular prism starting at the origin.
%C A107069 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).
%e A107069 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).
%e A107069 a(1) = 4 because (using the terminology in the Comment), the 4 possible 1-step walks are W_1 = {l,r,c,c-}.
%e A107069 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}.
%e A107069 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.
%o A107069 (Python)
%o A107069 w = [[[(0, 0)]]]
%o A107069 for n in range(1, 15):
%o A107069     nw = []
%o A107069     for walk in w[-1]:
%o A107069         (x, t) = walk[-1]
%o A107069         nss = [(x-1, t), (x+1, t), (x, (t+1)%3), (x, (t-1)%3)]
%o A107069         for ns in nss:
%o A107069             if ns not in walk:
%o A107069                 nw.append(walk[:] + [ns])
%o A107069     w.append(nw)
%o A107069 print([len(x) for x in w])
%o A107069 # _Andrey Zabolotskiy_, Sep 19 2019
%Y A107069 Cf. A002902, A002903, A077817, A038577, A302408, A007825.
%K A107069 nonn,walk
%O A107069 0,2
%A A107069 _Jonathan Vos Post_, May 10 2005
%E A107069 a(4) and a(5) corrected, a(6)-a(14) added by _Andrey Zabolotskiy_, Sep 19 2019
%E A107069 More terms from _Andrey Zabolotskiy_, Dec 04 2023