|
%I #53 Dec 20 2020 02:21:07
%S 1,2,3,5,8,13,21,34,55,89,141,226,362,580,921,1468,2344,3740,5922,
%T 9413,14978,23829,37686,59770,94882,150606,237947,376784,597063,
%U 946086,1493497,2361970,3737699,5914635,9330438,14741315,23301716,36833270,58071568
%N Number of self-avoiding walks of length n on square lattice such that at each point the angle turns 90 degrees (the first turn is assumed to be to the left - otherwise the number must be doubled).
%C The number of snakes composed of n identical segments such that the snake starts with a left turn and the other (n-2) joints are bent at 90-degree angles, either to the left or to the right, in such a way that the snake does not overlap.
%C Vi Hart came up with this idea of snakes (see the link below).
%H Vaclav Kotesovec, <a href="/A189722/b189722.txt">Table of n, a(n) for n = 2..50</a>
%H Vi Hart, <a href="http://vihart.com/blog/how-to-snakes/">How To Snakes</a> [Broken link?]
%H Vi Hart, <a href="https://www.youtube.com/watch?v=Gx5D09s5X6U">How to snakes</a>, YouTube, March 2011.
%H IBM Corp., <a href="http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/April2011.html">Ponder This</a>, April 2011.
%e For n=2 the a(2)=1 there is only one snake:
%e (0,0), (0,1), (-1,1).
%e For n=3 the a(3)=2 there are two snakes:
%e (0,0), (0,1), (-1,1), (-1,0);
%e (0,0), (0,1), (-1,1), (-1,2).
%e Representing the walk (or snake) as a sequence of turns I and -I in the complex plane, with the initial condition that the first turn is I, for length 2 we have [I], for length 3 we have [I,I], [I,-I], and for length 4 we have [I,I,-I], [I,-I,I], [I,-I,-I].
%p ValidSnake:=proc(P) local S, visited, lastdir, lastpoint, j;
%p S:={0, 1}; lastdir:=1; lastpoint:=1;
%p for j from 1 to nops(P) do lastdir:=lastdir*P[j];
%p lastpoint:=lastpoint+lastdir;
%p S:=S union {lastpoint};
%p od;
%p if (nops(S) = (2+nops(P))) then return(true); else return(false); fi;
%p end;
%p NextList:=proc(L) local S, snake, newsnake;
%p S:={ };
%p for snake in L do
%p newsnake:=[op(snake), I];
%p if ValidSnake(newsnake) then S:=S union {newsnake}; fi;
%p newsnake:=[op(snake), -I];
%p if ValidSnake(newsnake) then S:=S union {newsnake}; fi;
%p od;
%p return(S union { });
%p end;
%p L:={[I]}:
%p for k from 3 to 25 do
%p L:=NextList(L):
%p print(k, nops(L));
%p od:
%p # second Maple program:
%p a:= proc(n) local v, b;
%p v:= proc() true end: v(0, 0), v(0, 1):= false$2:
%p b:= proc(n, x, y, d) local c;
%p if v(x, y) then v(x, y):= false;
%p c:= `if`(n=0, 1,
%p `if`(d=1, b(n-1, x, y+1, 2) +b(n-1, x, y-1, 2),
%p b(n-1, x+1, y, 1) +b(n-1, x-1, y, 1) ));
%p v(x, y):= true; c
%p else 0 fi
%p end;
%p b(n-2, -1, 1, 1)
%p end:
%p seq(a(n), n=2..25); # _Alois P. Heinz_, Jun 10 2011
%t a[n_] := Module[{v, b}, v[_, _] = True; v[0, 0] = v[0, 1] = False; b[m_, x_, y_, d_] := Module[{c}, If[v[x, y], v[x, y] = False; c = If[m == 0, 1, If[d == 1, b[m-1, x, y+1, 2] + b[m-1, x, y-1, 2], b[m-1, x+1, y, 1] + b[m-1, x-1, y, 1]]]; v[x, y] = True; c, 0]]; b[n-2, -1, 1, 1]]; Table[ a[n], {n, 2, 25}] (* _Jean-François Alcover_, Nov 07 2015, after _Alois P. Heinz_ *)
%K nonn,walk
%O 2,2
%A _Dan Dima_ and _Stephen C. Locke_, Apr 25-26 2011
%E a(33)-a(40) from _Alois P. Heinz_, Jun 10 2011
|
