A272265 Number of n-step tri-directional self-avoiding walks on the hexagonal lattice.

1, 3, 9, 21, 51, 123, 285, 669, 1569, 3603, 8343, 19335, 44193, 101577, 233697, 532569, 1218345, 2789475, 6343161, 14464101, 33004269, 74923059, 170440203, 387945747, 879473277, 1997066751, 4536975315, 10273846185

Offset: 0

Author

Francois Alcover, May 05 2016

Keywords

• nonn
• walk
• more

Comments

Only 3 directions are allowed, separated by 120 degrees.

o

x

o o

Crossrefs

Cf. A001334.

Programs

Mathematica

mo={{2, 0},{-1, 1}, {-1, -1}}; a[0]=1;
a[tg_, p_:{{0, 0}}] := Block[{e, mv = Complement[Last[p]+# & /@ mo, p]}, If[tg == 1, Length@mv, Sum[a[tg-1, Append[p, e]], {e, mv}]]];
a /@ Range[0, 10]
(* Robert FERREOL, Nov 28 2018; after the program of Giovanni Resta in A001411 *)

Python

def add(L, x):
    M=[y for y in L]; M.append(x)
    return(M)
plus=lambda L, M : [x+y for x, y in zip(L, M)]
mo=[[2, 0], [-1, 1], [-1, -1]]
def a(n, P=[[0, 0]]):
    if n==0: return(1)
    mv1 = [plus(P[-1], x) for x in mo]
    mv2=[x for x in mv1 if x not in P]
    if n==1: return(len(mv2))
    else: return(sum(a(n-1, add(P, x)) for x in mv2))
print([a(n) for n in range(11)])
# Robert FERREOL, Nov 30 2018