Self-avoiding walks

[David W. Wilson]

Felice Russo wrote:

> Can someone help me to extend the sequences A034165, A034166, A034010 on
> particular self-avoiding walks?
> Thanks and regards.   Felice

I think your indexing of A034165 is nonstandard.  Judging from
your sequence values, you apparently interpret a 3x3 lattice to contain
16 points (the lattice points on a 3x3 grid of squares), whereas the
standard interpretation of a 3x3 lattice is 9 points arranged in a
square.  Thus I would reindex A034165 to accomodate the standard
interpretation.  I would also prepend an initial 1 to count the number
of paths on a 1x1 lattice (consisting of 1 point).  So I get

%S A034165 1,2,2,4,10,36,188,1582,20576,388592
%O A034165 1,2

Also, I get a(6) = 36 compared to your a(6) = 30.  I defense of my value,
here is a list of the 36 valid walks from the lower left to upper right
corner of a 6x6 lattice:

RULURULURURDRDLDRDRURULURU
RULURULURURDRDRURU
RULURULURURDRURDRU
RULURURDRDRURULURU
RULURURDRURURU
RULURURURDRURU
RULURURURURDRU
RURDRURULULDLULURURDRURDRU
RURDRURULULURURDRU
RURDRURULURURU
RURDRURURULURU
RURULULURURDRDRURU
RURULULURURDRURDRU
RURULURURDRURU
RURULURURURDRU
RURURDRURULURU
RURURULURURDRU
RURURURURU
URDRURDRURULULDLULURURDRUR
URDRURDRURULULURUR
URDRURDRURULURULUR
URDRURULULURURDRUR
URDRURULURURUR
URDRURURULURUR
URDRURURURULUR
URULURURDRDLDRDRURULURULUR
URULURURDRDRURULUR
URULURURDRURUR
URULURURURDRUR
URURDRDRURULULURUR
URURDRDRURULURULUR
URURDRURULURUR
URURDRURURULUR
URURULURURDRUR
URURURDRURULUR
URURURURUR

My program is a dumb counter, which takes > O(a(n))
time to compute a(n).  However, an approach based on finite automata
could compute a(n) in about O(log(a(n)).  I used this approach,
for instance, to compute large terms of A018807.  Unfortunately,
initializing such a program is rather painful, so I didn't bother here.

For A034166 I get

%S A034166 0,2,4,10,12,26,36,46,60,82
%O A034166 1,2

I think this sequence is probably much more tractable.  I am all but
certain that you will find that this sequence is a linear recurrence.