How to calculate a number of all possible random walks without self-intersections?

213 Views Asked by At

Is there a certain formula, that gives number of all possible non-self-intersected N walks?

N is number of steps of the walk. Grid is endless, size doesn't matter.

Random walks in the rectangle grid. enter image description here

Superposition of all possible self-avoiding walks for N=3(each begin from same point) enter image description here

First I thought, it should be something like $P=P_{prev}+(P_{prev}*3)$(P - number of possible walks), but it's wrong, because number of possible walks for N=3 is 28 but not 64