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
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