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!)
 A175941 Number of n-step self-avoiding walks on a line, where step X skips X - 1 spaces. 1
 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, 2953094, 4897922, 8157096, 13571014, 22552212, 37486916, 62325564, 103508754, 172765524, 287428656, 479052200, 798944976 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 LINKS FORMULA a(n) <= 2*a(n-1) for n > 0. - Andrew Howroyd, Nov 12 2018 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 (PARI) a(n)={local(f=vectorsmall(n*(n+1)+1)); my(recurse(p, k)=if(!f[p], if(k==n, 1, f[p]=1; k++; my(z=self()(p+k, k) + self()(p-k, k)); f[p]=0; z))); recurse((#f+1)/2, 0)} \\ Andrew Howroyd, Nov 12 2018 CROSSREFS Cf. A321535. Sequence in context: A025052 A142584 A098197 * A317536 A203175 A102477 Adjacent sequences:  A175938 A175939 A175940 * A175942 A175943 A175944 KEYWORD nonn,walk AUTHOR Grant Garcia, Oct 25 2010 EXTENSIONS a(29)-a(40) from Andrew Howroyd, Nov 12 2018 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 May 9 05:01 EDT 2021. Contains 343688 sequences. (Running on oeis4.)