Self Avoiding Walks

Today I turned 26590 old and one of the properties of this number is that its a member of OEIS A191823 where \(n=10\):

A191823

Number of \(n\)-step three-sided prudent self-avoiding walks.

The initial members of the sequence are 1, 4, 12, 34, 90, 236, 612, 1580, 4060, 10404, 26590, 67820, 172654, 438842, ...

This set me off to find out what exactly what is meant by the terms used to describe members of this particular OEIS. Here is what I came up with (source):

• A self-avoiding walk (SAW) is a sequence of moves on a lattice not visiting the same point more than once. See Figure 1.
  
  

  

  Figure 1: source

  
  
• A SAW on the square lattice is prudent if it never takes a step towards a vertex it has already visited. See Figure 2 for an explanation of why the SAW in Figure 1 is not prudent.

Figure 2: this is NOT a prudent SAW

• The box of a square lattice walk is the smallest rectangle that contains it. It is not hard to see that the endpoint of a prudent walk is always on the border of the box. This means that every new step either walks on the border of the box, of moves one of its four sides. Observe that a prudent walk is partially directed if its endpoint, as the walk grows, always lies on the top side of the box. This is why these walks are also called one-sided. See Figure 3

Figure 3: one-sided prudent SAW

Similarly, a prudent walk is two-sided if its endpoint, as the walk grows, lies always on the top or right side of the box. See Figure 4.

Figure 4: two-sided prudent SAW

It is three-sided if its endpoint, as the walk grows, is always on the top, right or left side of the box. See Figure 5. Of course, four-sided walks coincide with general prudent walks. See Figure 3 for examples of these. See Figure 6.

Figure 5: three-sided prudent SAW

Figure 6: four-sided prudent SAW

There is much research going into the study of these walks but I don't want to go into more detail here. I just wanted to get clear in my head what is a SAW, a PSAW and one-sided, two-sided, three-sided and four-sided PSAW.