login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 0

%I

%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 Hart V., <a href="http://vihart.com/blog/how-to-snakes/">How To Snakes</a>

%H IBM Corp., <a href="http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/April2011.html">Ponder This</a>

%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

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 24 06:31 EDT 2014. Contains 248502 sequences.