The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 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). 3
 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, 226, 362, 580, 921, 1468, 2344, 3740, 5922, 9413, 14978, 23829, 37686, 59770, 94882, 150606, 237947, 376784, 597063, 946086, 1493497, 2361970, 3737699, 5914635, 9330438, 14741315, 23301716, 36833270, 58071568 (list; graph; refs; listen; history; text; internal format)
 OFFSET 2,2 COMMENTS 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. Vi Hart came up with this idea of snakes (see the link below). LINKS Vaclav Kotesovec, Table of n, a(n) for n = 2..50 Vi Hart, How To Snakes [Broken link?] Vi Hart, How to snakes, YouTube, March 2011. IBM Corp., Ponder This, April 2011. EXAMPLE For n=2 the a(2)=1 there is only one snake: (0,0), (0,1), (-1,1). For n=3 the a(3)=2 there are two snakes: (0,0), (0,1), (-1,1), (-1,0); (0,0), (0,1), (-1,1), (-1,2). 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]. MAPLE ValidSnake:=proc(P) local S, visited, lastdir, lastpoint, j; S:={0, 1}; lastdir:=1; lastpoint:=1; for j from 1 to nops(P) do  lastdir:=lastdir*P[j];   lastpoint:=lastpoint+lastdir;   S:=S union {lastpoint}; od; if (nops(S) = (2+nops(P))) then return(true); else return(false); fi; end; NextList:=proc(L) local S, snake, newsnake; S:={ }; for snake in L do   newsnake:=[op(snake), I];   if ValidSnake(newsnake) then S:=S union {newsnake}; fi;   newsnake:=[op(snake), -I];   if ValidSnake(newsnake) then S:=S union {newsnake}; fi; od; return(S union { }); end; L:={[I]}: for k from 3 to 25 do   L:=NextList(L):   print(k, nops(L)); od: # second Maple program: a:= proc(n) local v, b;       v:= proc() true end: v(0, 0), v(0, 1):= false\$2:       b:= proc(n, x, y, d) local c;             if v(x, y) then v(x, y):= false;                c:= `if`(n=0, 1,                    `if`(d=1, b(n-1, x, y+1, 2) +b(n-1, x, y-1, 2),                              b(n-1, x+1, y, 1) +b(n-1, x-1, y, 1) ));                v(x, y):= true; c             else 0 fi           end;       b(n-2, -1, 1, 1)     end: seq(a(n), n=2..25);  # Alois P. Heinz, Jun 10 2011 MATHEMATICA 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 *) CROSSREFS Sequence in context: A232666 A093091 A105471 * A023441 A268133 A217737 Adjacent sequences:  A189719 A189720 A189721 * A189723 A189724 A189725 KEYWORD nonn,walk AUTHOR Dan Dima and Stephen C. Locke, Apr 25-26 2011 EXTENSIONS a(33)-a(40) from Alois P. Heinz, Jun 10 2011 STATUS approved

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

Last modified July 23 21:01 EDT 2021. Contains 346262 sequences. (Running on oeis4.)