A359709 Number of n-step self-avoiding walks on a 2D square lattice whose end-to-end distance is an integer.

1, 4, 4, 12, 28, 76, 164, 732, 1044, 4924, 6724, 30636, 43972, 190516, 313996, 1197908, 2284260, 7678188, 16257604, 50524252, 113052396, 341811828, 773714436, 2358452388, 5245994292, 16447462492, 35395532236, 115129727188, 238542983748, 804980005276

Offset: 0

Author

Scott R. Shannon, Jan 12 2023

Keywords

• nonn
• walk

Comments

The walks counted are all those directly along and x or y axes, and all walks whose final (|x|,|y|) lattice point are the two legs of a Pythagorean triple.

Examples

			a(3) = 12 as, in the first quadrant, there is one 3-step SAW whose end-to-end distance is an integer (1 unit):
.
     X---.
         |
     X---.
.
This can be walked in 8 different ways on a 2D square lattice. There are also the four walks directly along the x and y axes, giving a total of 8 + 4 = 12 walks.
		

Links

• Wikipedia, Self-avoiding walk.

Crossrefs

Cf. A359073, A103606, A359741, A001411, A356617, A173380, A337353, A358036, A358046.