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

Table of n, a(n) for n=2..40.

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 21 01:33 EST 2019. Contains 329349 sequences. (Running on oeis4.)