A293865 Number of self-intersecting walks of length n on a square lattice such that at each point the angle turns 90 degrees.

0, 0, 0, 1, 1, 2, 3, 5, 8, 13, 21, 37, 56, 90, 144, 239, 374, 592, 948, 1558, 2431, 3848, 6127, 9972, 15602, 24658, 39158, 63265, 99110, 156505, 248040, 398675, 625024, 986241, 1560763, 2498832, 3919561, 6180914, 9770162, 15594972, 24470070, 38567903, 60907330

Offset: 1

Author

Jens Randrup Rasmussen, Oct 18 2017

Keywords

• nonn
• walk

Comments

It is assumed that the first walk turns left and that all walks end when they intersect themselves.

Examples

			For n = 4 we have the simplest self-intersecting walk, which is a square.
For n = 5 we have the walk:
(0,0), (0,1), (-1,1), (-1, 2), (0,2), (0,1)
For n = 6 we have the walks:
(0,0), (0,1), (-1,1), (-1, 0), (-2,0), (-2,1), (-1,1)
(0,0), (0,1), (-1,1), (-1, 2), (-2,2), (-2,1), (-1,1)
		

Links

• MathStackExchange, Expected Number of Steps Before Intersection, Oct 2017.

Crossrefs

This sequence gives the number of self-intersecting walks while A189722 gives the number of self-avoiding walks.

Formula

For n>2, a(n) = 2*A189722(n-1) - A189722(n). - Jens Randrup Rasmussen, Oct 29 2017

Extensions

The terms starting from a(11) and the program corrected by Jens Randrup Rasmussen, Oct 29 2017