

A175941


Number of nstep selfavoiding walks on a line, where step X skips X  1 spaces.


0



1, 2, 4, 6, 10, 18, 30, 50, 78, 130, 210, 350, 586, 954, 1606, 2588, 4234, 6944, 11342, 18948, 31450, 52206, 85662, 141680, 233040, 385428, 644910, 1072074, 1783342
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


LINKS

Table of n, a(n) for n=0..28.


EXAMPLE

a(0) = 1 because every walk must start at a specific point on the line.
0
a(1) = 2 because there are two ways to start, moving one space forward or backward.
01
10
a(2) = 4 because there are two ways to continue each of the walks described in a(1).
012
201
102
210
a(3) = 6, not 8, because two of the possible four continuations are not selfavoiding.
0123
2013
3201
1023
3102
3210


PROG

(Python) x = 1
n = 0
runs = [[n]]
while x < 30:
.print x  1, n
.runs2 = []
.n = 0
.while len(runs) > 0:
..for pmx in (x, x):
...if runs[0][ 1] + pmx not in runs[0]:
....runs2.append(runs[0] + [runs[0][ 1] + pmx])
....n += 1
..del runs[0]
.runs = runs2
.x += 1


CROSSREFS

Sequence in context: A025052 A142584 A098197 * A203175 A102477 A232582
Adjacent sequences: A175938 A175939 A175940 * A175942 A175943 A175944


KEYWORD

more,nonn,walk


AUTHOR

Grant Garcia, Oct 25 2010


STATUS

approved



