login
Possible traces of n-step walks on 1-D lattice, ignoring translations.
1

%I #7 Jun 06 2021 20:47:38

%S 1,2,4,7,14,23,45,72,137,217,402,635,1149,1816,3221,5101,8898,14127,

%T 24305,38688,65809,105009,176962,282995,473269,758312,1260253,2022661,

%U 3344354,5375207

%N Possible traces of n-step walks on 1-D lattice, ignoring translations.

%C Translations discounted, so the sequence of visits <0,1,2,1,0> has trace (2,2), as do <0,-1,0,1,0>, <0,-1,-2,-1,0>, etc.

%C Trace as used here refers to the number of times an edge is used in the walk. - _Sean A. Irvine_, Jun 06 2021

%H Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a048/A048248.java">Java program</a> (github)

%e a(4)=7 since a walk of 4 steps can leave traces (1,1,1,1), (1,1,2), (2,1,1), (2,2), (1,3), (3,1) and (4). Note that (1,2,1) is impossible.

%t For[size = 1, size < 10, size++, traces = {}; For[i = 0, i < 2^ size, i++, thePath = IntegerDigits[i, 2, size]*2 - 1; loc = size + 2; theTrace = Table[0, {z, -size - 1, size + 1}]; For[j = 1, j <= size, j++, loc += thePath[[j]]; If[thePath[[j]] == 1, theTrace[[loc - 1]]++, theTrace[[loc]]++ ];]; theTrace = Select[theTrace, # > 0 &]; If[ ! MemberQ[traces, theTrace], traces = Append[traces, theTrace]];]; Print[Length[traces]]]; - Sam Handler (sam_5_5_5_0(AT)yahoo.com), Aug 17 2006

%K nonn,more

%O 1,2

%A _Tony Bartoletti_

%E a(19)-a(21) from Sam Handler (sam_5_5_5_0(AT)yahoo.com), Aug 17 2006

%E a(22)-a(30) from _Sean A. Irvine_, Jun 06 2021