This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
a(1) = 0 as after one step in any of the four available directions the first and last point of the walk are directly connected by a line forming the path, so are not considered mutually visible.
a(2) = 8 as there are 4*3 = 12 2-step SAWs, but the four walks which consist of two steps directly along the axes have a visited lattice point directly between the first and last points of the walk, so those two point are not visible from each other. Thus a(2) = 12 - 4 = 8.
a(3) = 24 as there are thirty-six 3-step SAWs which include four walks directly along the axes which have a first point that is not visible from the last. In the first quadrant there is one other walk whose second-step path is intersected by the line between the first and last points of the walk. This walk is:
.
.---X
|
X---.
.
where the first and last points are shown as 'X'. The above walk can be walked in eight ways on the 2D square lattice, so the total number of walks where the first point is visible from the last is 36 - 4 - 1*8 = 36 - 12 = 24.
a(4) = 48 as there are one hundred 4-step SAWs which include four walks directly along the axes which have a first point that is not visible from the last. In the first quadrant there are six other walks which have either previously visited points directly on the line between the first and last points of the walk, or in which this line intersects the path of previous steps. These walks are:
.
X .---X X
| | |
@---. @ @---. .---.---X .---. .---X
| | | | | | |
X---. X---. X---. X---. X---@ X X---.---.
.
where the visited points on the line between the first and last points are shown as '@'. Each of the above walks can be walked in eight ways on the 2D square lattice, so the total number of walks where the first point is visible from the last is 100 - 4 - 6*8 = 100 - 52 = 48.
a(1) = 4 as after one step in any of the four available directions the lattice point stepped to and the starting point have no other points between them, so the first point is visible from the last for all four walks.
a(2) = 8 as there are 4*3 = 12 2-step SAWs, but the four walks which consist of two steps directly along the axes have a visited lattice point directly between the first and last points of the walk, so those two point are not visible from each other. Thus a(2) = 12 - 4 = 8.
a(3) = 32 as there are thirty-six 3-step SAWs, and of those, only the four walks directly along the axes have visited points between the first and last points, so a(3) = 36 - 4 = 32.
a(4) = 64 as there are one hundred 4-step SAWs which include four walks directly along the axes which have a first point that is not visible from the last. In the first quadrant there are four other walks which have points on the line between the first and last point, and these points have been visited by earlier steps. These walks are:
.
X .---X X
| | |
@---. @ @---. .---.
| | | | |
X---. X---. X---. X---@ X
.
where the first and last points are shown as 'X' and where the visited points on the line between these two points are shown as '@'. Each of the above walks can be walked in eight ways on the 2D square lattice, so the total number of walks where the first point is visible from the last is 100 - 4 - 4*8 = 100 - 36 = 64.
(* b = A001411 *) mo = Tuples[{-1, 1}, 2]; b[0] = 1; b[tg_, p_:{{0, 0}}] := b[tg, p] = Block[{e, mv = Complement[Last[p] + #& /@ mo, p]}, If[tg == 1, Length[mv], Sum[b[tg-1, Append[p, e]], {e, mv}]]]; a[n_] := b[n]/2; Table[an = a[n]; Print[an]; an, {n, 1, 16}] (* Jean-François Alcover, Nov 02 2018, after Giovanni Resta in A001411 *)
There are 6 paths of length 2 on the (4,6,12) lattice corresponding to the reduced words in the Coxeter group s_0 s_2, s_0 s_1, s_1 s_2, s_1 s_0, s_2 s_0, s_2 s_1.
a(1) = 2 because there are only two possible directions at each intersection; for the same reason a(2) = 2*2 and a(3) = 2*4 ; but a(4) = 12 (not 16) because four paths return to the starting point and are not self-avoiding. See the 12 paths under "links".
walks:=proc(n)
option remember;
local i,father,End,X,walkN,dir,u,x,y;
if n=1 then [[[0,0]]] else
father:=walks(n-1):
walkN:=NULL:
for i to nops(father) do
u:=father[i]:End:=u[n-1]:if n mod 2 = 0 then
dir:=[[1,0], [-1, 0]] else dir := [[0,1], [0, -1]] fi:
for X in dir do
if not(member(End+X,u)) then walkN:=walkN,[op(u),End+X] fi;
od od:
[walkN] fi end:
n:=5:L:=walks(n):N:=nops(L);
# This program explicitly gives the a(n) walks.
mo = {{1, 0}, {-1, 0}}; moo = {{0, 1}, {0, -1}}; a[0] = 1;
a[tg_, p_: {{0, 0}}] := Module[{e, mv},
If[Mod[tg, 2] == 0, mv = Complement[Last[p] + # & /@ mo, p],
mv = Complement[Last[p] + # & /@ moo, p]];
If[tg == 1, Length@mv, Sum[a[tg - 1, Append[p, e]], {e, mv}]]];
a /@ Range[0, 20] (* after the program from Giovanni Resta at A001411 *)
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 = [[1, 0], [-1, 0]]
moo = [[0, 1], [0, -1]]
def a(n, P=[[0, 0]]):
if n == 0:
return 1
if n % 2 == 0:
mv1 = [plus(P[-1], x) for x in mo]
else:
mv1 = [plus(P[-1], x) for x in moo]
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)
[a(n) for n in range(21)]
Comments