|
%I #23 Jan 07 2019 03:23:46
%S 1,8,56,360,2240,13696,82808,496656,2961136,17573608,103911424,
%T 612577272,3602222736,21137815952,123811421128,724064474968,
%U 4228582808424
%N Number of n-step self-avoiding nonintersecting walks on the square lattice with diagonals allowed (corresponds to using the Moore neighborhood).
%C The path cannot return to a lattice point nor intersect with itself (which IS allowed in A272763).
%C The Moore neighborhood characterizes king tours. - _Rainer Rosenthal_, Jan 06 2019
%p # For starting point stp and list Ldir of n directions (1..8)
%p # construct the points of the whole path and count them.
%p # In order to avoid crossings consider the n midpoints, too.
%p # If there are 2*n+1 then the path is self-avoiding and uncrossed.
%p isNice := proc(Ldir) local Delta, dir, ep, mp, path;
%p Delta := [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]];
%p ep := [0,0]; path := {ep};
%p for dir in Ldir do
%p mp := ep + Delta[dir];
%p ep := mp + Delta[dir];
%p path := {op(path), mp, ep};
%p od;
%p return evalb(nops(path)=2*nops(Ldir)+1);
%p end:
%p # Count only king tours which are nice, i.e. self-avoiding and uncrossed.
%p A272773 := proc(n) local count, T, p;
%p count := 0:
%p T := combinat[cartprod]([seq([$1..8], j=1..n)]):
%p while not T[finished] do
%p p := T[nextvalue]();
%p if isNice(p) then count := count+1; fi;
%p od:
%p return count;
%p end: # _Rainer Rosenthal_, Jan 06 2019
%t mo = Most@Tuples[{-1, 1, 0}, 2]; a[0] = 1; a[tg_, p_: {{0, 0}}] := Block[{e, z = Last@p, w, mv = {}}, Do[w = {z+e, z+2*e}; If[Intersection[w, p] == {}, AppendTo[mv, w]], {e, mo}]; If[tg == 1, Length[mv], Sum[a[tg-1, Join[p, e]], {e, mv}]]]; a /@ Range[0, 7] (* Corrected following a suggestion by _Rainer Rosenthal_, _Giovanni Resta_, Jan 06 2019 *)
%Y Cf. A272763, A001411, A323140, A323141.
%K nonn,walk,more
%O 0,2
%A _Giovanni Resta_, May 06 2016
%E a(5)-a(7) corrected by _Rainer Rosenthal_, Jan 06 2019
%E a(8)-a(16) from _Hugo Pfoertner_, Jan 06 2019
|
