This is a random walk on the lattice of integer points in the plane. At each stage, there is a probability 1/4 of moving to each of the four adjacent points. There are  possible paths (starting at the origin) of length n. The number of these that end at the point (j,k) is 0 if or if is odd. If is even then the number of paths ending at (j,k) is  .

I guessed that formula by working out what happens for small values of n (2,3,4 and 5). My iit proffessor proved it by induction on n, by using the recurrence relation ,

where N(n;j,k) is the number of paths of length n ending at (j,k). It follows from the standard  property of binomial coefficients, .

So, the probability that the man is one step away from where he started after 9 steps is .