cp's OEIS Frontend

A189722 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).

%I A189722 #57 Dec 02 2024 16:29:52
%S A189722 1,2,3,5,8,13,21,34,55,89,141,226,362,580,921,1468,2344,3740,5922,
%T A189722 9413,14978,23829,37686,59770,94882,150606,237947,376784,597063,
%U A189722 946086,1493497,2361970,3737699,5914635,9330438,14741315,23301716,36833270,58071568
%N A189722 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 A189722 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 A189722 Vi Hart came up with this idea of snakes (see the link below).
%H A189722 Vaclav Kotesovec, <a href="/A189722/b189722.txt">Table of n, a(n) for n = 2..50</a>
%H A189722 Vi Hart, <a href="http://vihart.com/blog/how-to-snakes/">How To Snakes</a> [Broken link?]
%H A189722 Vi Hart, <a href="https://www.youtube.com/watch?v=Gx5D09s5X6U">How to snakes</a>, YouTube, March 2011.
%H A189722 IBM Corp., <a href="https://research.ibm.com/haifa/ponderthis/challenges/April2011.html">Ponder This</a>, April 2011.
%e A189722 For n=2 the a(2)=1 there is only one snake:
%e A189722 (0,0), (0,1), (-1,1).
%e A189722 For n=3 the a(3)=2 there are two snakes:
%e A189722 (0,0), (0,1), (-1,1), (-1,0);
%e A189722 (0,0), (0,1), (-1,1), (-1,2).
%e A189722 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 A189722 ValidSnake:=proc(P) local S, visited, lastdir, lastpoint, j;
%p A189722 S:={0, 1}; lastdir:=1; lastpoint:=1;
%p A189722 for j from 1 to nops(P) do  lastdir:=lastdir*P[j];
%p A189722   lastpoint:=lastpoint+lastdir;
%p A189722   S:=S union {lastpoint};
%p A189722 od;
%p A189722 if (nops(S) = (2+nops(P))) then return(true); else return(false); fi;
%p A189722 end;
%p A189722 NextList:=proc(L) local S, snake, newsnake;
%p A189722 S:={ };
%p A189722 for snake in L do
%p A189722   newsnake:=[op(snake), I];
%p A189722   if ValidSnake(newsnake) then S:=S union {newsnake}; fi;
%p A189722   newsnake:=[op(snake), -I];
%p A189722   if ValidSnake(newsnake) then S:=S union {newsnake}; fi;
%p A189722 od;
%p A189722 return(S union { });
%p A189722 end;
%p A189722 L:={[I]}:
%p A189722 for k from 3 to 25 do
%p A189722   L:=NextList(L):
%p A189722   print(k, nops(L));
%p A189722 od:
%p A189722 # second Maple program:
%p A189722 a:= proc(n) local v, b;
%p A189722       v:= proc() true end: v(0, 0), v(0, 1):= false$2:
%p A189722       b:= proc(n, x, y, d) local c;
%p A189722             if v(x, y) then v(x, y):= false;
%p A189722                c:= `if`(n=0, 1,
%p A189722                    `if`(d=1, b(n-1, x, y+1, 2) +b(n-1, x, y-1, 2),
%p A189722                              b(n-1, x+1, y, 1) +b(n-1, x-1, y, 1) ));
%p A189722                v(x, y):= true; c
%p A189722             else 0 fi
%p A189722           end;
%p A189722       b(n-2, -1, 1, 1)
%p A189722     end:
%p A189722 seq(a(n), n=2..25);  # _Alois P. Heinz_, Jun 10 2011
%t A189722 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 A189722 nonn,walk
%O A189722 2,2
%A A189722 _Dan Dima_ and _Stephen C. Locke_, Apr 25-26 2011
%E A189722 a(33)-a(40) from _Alois P. Heinz_, Jun 10 2011