A321535 -id:A321535 - cp's OEIS frontend

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

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

Offset: 0

Grant Garcia, Oct 25 2010

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

Cf. A321535.

b:= proc(n, s) option remember; `if`(n=0, 1, add(`if`(j in s, 0,
      b(n-1, {map(x-> x-j, s)[], 0})), j=(k->[-k, k])(nops(s))))
    end:
a:= n-> b(n, {0}):
seq(a(n), n=0..24);  # Alois P. Heinz, May 19 2021

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]}}]];
a[n_] := b[n, {0}];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 28}] (* Jean-François Alcover, Jul 09 2021, after Alois P. Heinz *)

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

x = 1
n = 0
runs = [[n]]
while x < 30:
    print(x - 1, n)
    runs2 = []
    n = 0
    while runs:
        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

a(n) <= 2*a(n-1) for n > 0. - Andrew Howroyd, Nov 12 2018

a(29)-a(40) from Andrew Howroyd, Nov 12 2018

A360255 Irregular triangle (an infinite binary tree) read by rows: see Comments section for definition.

Original entry on oeis.org

0, 1, 3, 6, 2, 10, 7, 5, 15, 13, 11, 9, 21, 20, 4, 18, 2, 16, 14, 28, 12, 28, 12, 26, 8, 24, 22, 20, 36, 21, 19, 37, 21, 17, 35, 17, 33, 13, 31, 11, 29, 27, 45, 11, 31, 9, 29, 27, 47, 31, 7, 27, 25, 45, 7, 27, 23, 43, 23, 41, 19, 39, 17, 37, 35, 55, 22, 42, 18

Offset: 0

John Tyler Rascoe, Jan 30 2023

The binary tree has root node 0, in row n=0. The left child is m - n and the right child is m + n, where m is the parent node and n is the row of the child. A given node will only have a child if the child is nonnegative and the value of the child is not present in the path from the parent to the root, including the root value itself.

The n-th row will have A321535(n) nodes. The rightmost border is A000217.

			The binary tree starts with root 0 in row n = 0. In row n = 3, the parent node m = 3 does not have a left child since 3 - 3 = 0 is included in the path from the parent to the root {3,1,0}.
The tree begins:
row
[n]
[0]           0
               \
[1]             1
                 \
[2]               3
                   \
[3]               __6__
                 /     \
[4]             2      10
                 \    /  \
[5]               7  5    15

Rémy Sigrist, Table of n, a(n) for n = 0..9517 (rows for n = 0..21 flattened)

Cf. A000217, A141001, A141002, A321535, A360173.

function a = A360255( max_row )
    p = 0; a = 0; pos = 1;
    for n = 1:max_row
        for k = pos:length(a)
            h =[]; o = p(k);
            while o > 0
                h = [h a(o)]; o = p(o);
            end
            if a(k)-n > 0
                if isempty(find(h == a(k)-n, 1))
                    p = [p k]; a = [a a(k)-n];
                end
            end
            if isempty(find(h == a(k)+n, 1))
                p = [p k]; a = [a a(k)+n];
            end
        end
        pos = k+1;
    end
end % Thomas Scheuerle, Jan 31 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions