I am trying to compute the number of 5-step self avoiding walks on dimension d. I have computed the number of 1-step SAW which is 2d. For 2-steps it is $2d(2d-1)$. For 3-steps it is $2d(2d-1)^2$, which are easy to compute.
For computing the number of 4-step SAWs I looked to d=2. There are $4*3*3*3 = 108$ possible walks but in 8 cases the walk returns to the origin so there are 100 possible SAWs. I guess the number would be $2d(2d-1)^3-2^{d-1}$
Anyone know how to compute it for 5-step self avoiding walks?
As the number of times a walk of length 4 intersects with itself without going directly backwards is the amount of times it changes it's direction 3 times in the same way (only changing the direction to the left for example) this amount is 2d(2d-2) therefore the number would be 2d(2d-1)^3 - 2d(2d-2). For walks of length you can use the same logic to find the amount of walks which intersect at the fourth or fifth step.