1
$\begingroup$

Given a square grid of size $n \times n$, how many paths are there from one corner to a diagonally opposite corner?

I searched OEIS but was only able to find this. The numbers there reflect only non-intersecting paths. I'm interested in all paths.

Thoughts?

EDIT

A path may not traverse any edge it has previously traversed.

Only rook moves allowed.

$\endgroup$
  • $\begingroup$ Is a path allowed to retrace itself? If so, there are infinitely many paths. If not, then I think you need to specify more clearly what kinds of paths are allowed. $\endgroup$ – mweiss Jun 19 '18 at 21:33
  • $\begingroup$ @mweiss: It is not. I'll edit to reflect that. $\endgroup$ – Jens Jun 19 '18 at 21:35
  • 1
    $\begingroup$ How did you search OEIS? By text search, or by computing the first few terms and searching for them? If you haven't done the latter, you should try it; it shouldn't be too much work to get up to $n=3$, and that might narrow the search down enough to look through all the entries found. $\endgroup$ – joriki Jun 19 '18 at 22:53
  • 1
    $\begingroup$ By "rook moves" do you mean that a path can go from $(1,1)$ to $(3,1)$ directly, and this is different from going from $(1,1)$ to $(2,1)$ to $(3,1)$? $\endgroup$ – Misha Lavrov Jun 19 '18 at 23:49
  • 1
    $\begingroup$ @Joriki: Using your suggestion I found the sequence in OEIS. Thanks. $\endgroup$ – Jens Jun 20 '18 at 22:59

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.