# Number of 5-step self avoiding walks

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?