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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A175941 Number of n-step self-avoiding 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).

---01-2

--201--

--102--

2-10---

a(3) = 6, not 8, because two of the possible four continuations are not self-avoiding.

------01-2--3

-----2013----

--3--201-----

-----102--3--

----3102-----

3--2-10------

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

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 April 19 02:56 EDT 2014. Contains 240737 sequences.