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