cp's OEIS Frontend

A175941 Number of n-step self-avoiding walks on a line, where step X skips X - 1 spaces.

%I A175941 #20 Jul 09 2021 22:57:24
%S A175941 1,2,4,6,10,18,30,50,78,130,210,350,586,954,1606,2588,4234,6944,11342,
%T A175941 18948,31450,52206,85662,141680,233040,385428,644910,1072074,1783342,
%U A175941 2953094,4897922,8157096,13571014,22552212,37486916,62325564,103508754,172765524,287428656,479052200,798944976
%N A175941 Number of n-step self-avoiding walks on a line, where step X skips X - 1 spaces.
%F A175941 a(n) <= 2*a(n-1) for n > 0. - _Andrew Howroyd_, Nov 12 2018
%e A175941 a(0) = 1 because every walk must start at a specific point on the line.
%e A175941    --0--
%e A175941 a(1) = 2 because there are two ways to start, moving one space forward or backward.
%e A175941    --01-
%e A175941    -10--
%e A175941 a(2) = 4 because there are two ways to continue each of the walks described in a(1).
%e A175941    ---01-2
%e A175941    --201--
%e A175941    --102--
%e A175941    2-10---
%e A175941 a(3) = 6, not 8, because two of the possible four continuations are not self-avoiding.
%e A175941    ------01-2--3
%e A175941    -----2013----
%e A175941    --3--201-----
%e A175941    -----102--3--
%e A175941    ----3102-----
%e A175941    3--2-10------
%p A175941 b:= proc(n, s) option remember; `if`(n=0, 1, add(`if`(j in s, 0,
%p A175941       b(n-1, {map(x-> x-j, s)[], 0})), j=(k->[-k, k])(nops(s))))
%p A175941     end:
%p A175941 a:= n-> b(n, {0}):
%p A175941 seq(a(n), n=0..24);  # _Alois P. Heinz_, May 19 2021
%t A175941 b[n_, s_] := b[n, s] = If[n == 0, 1, Sum[If[MemberQ[s, j], 0, b[n - 1, Union[Append[s - j, 0]]]], {j, {-Length[s], Length[s]}}]];
%t A175941 a[n_] := b[n, {0}];
%t A175941 Table[Print[n, " ", a[n]]; a[n], {n, 0, 28}] (* _Jean-François Alcover_, Jul 09 2021, after _Alois P. Heinz_ *)
%o A175941 (Python)
%o A175941 x = 1
%o A175941 n = 0
%o A175941 runs = [[n]]
%o A175941 while x < 30:
%o A175941     print(x - 1, n)
%o A175941     runs2 = []
%o A175941     n = 0
%o A175941     while runs:
%o A175941         for pmx in (x, -x):
%o A175941             if runs[0][ -1] + pmx not in runs[0]:
%o A175941                 runs2.append(runs[0] + [runs[0][ -1] + pmx])
%o A175941                 n += 1
%o A175941         del runs[0]
%o A175941     runs = runs2
%o A175941     x += 1
%o A175941 (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
%Y A175941 Cf. A321535.
%K A175941 nonn,walk
%O A175941 0,2
%A A175941 _Grant Garcia_, Oct 25 2010
%E A175941 a(29)-a(40) from _Andrew Howroyd_, Nov 12 2018