How many paths are there between $(0,0)$ and $(n,n)$ if you include all eight common cardinal directions: North, East, South, West, Northeast, Northwest, Southeast, and Southwest. The only condition is if $(i,j)$ is in the path, $0≤i≤n$ and $0≤j≤n$, and if $(k,l)$ is also in the same path, both $i ≠ k$ and $j ≠ l$.

Ex ($n=1$):

We would have

$(0,0) => (0,1) => (1,1)$

$(0,0) => (1,0) => (1,1)$

$(0,0) => (1,1)$

$(0,0) => (0,1) => (1,0) => (1,1)$

$(0,0) => (1,0) => (0,1) => (1,1)$

So $a(1) = 5.$

(A good link is https://oeis.org/A007764 -- these are the number of paths with no diagonal movement.)

Are there any suggestions on how to approach this or other links with information? Thanks in advance!

  • $\begingroup$ Do you have to stay within the $n \times n$ box? If there's no restriction the answer is $\infty$ since you can go to Pluto and back to $(n,n)$. $\endgroup$ – Jair Taylor Apr 27 '15 at 7:20
  • $\begingroup$ Counting sets of self-avoiding walks is very, very hard in general so I would imagine this question is open. $\endgroup$ – Jair Taylor Apr 27 '15 at 7:21
  • $\begingroup$ @JairTaylor Yes, you have to stay in the circle... And okay, thanks. I figured but it seemed like it could be solved. $\endgroup$ – Derek Orr Apr 27 '15 at 19:19
  • $\begingroup$ box* not circle. $\endgroup$ – Derek Orr Apr 28 '15 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.