# Number of paths in a grid

A common puzzle problem is to count the number of paths that start from the bottom-left-hand corner of a grid and end at the top-right hand corner, with the restriction that you can only move upwards or rightwards.

For example, for a 3 by 3 grid (as shown below), the total number of ways is $\binom{6}{3}=20$

If we modify the problem to allow the path to contain downwards and leftwards moves, but maintain a restriction that you cannot visit an intersection twice, what is a general solution for the number of possible paths?

(In the case of the 3 by 3 grid below, I enumerated the total paths with a computer program and got 210).

-
This is called "self-avoiding rook walk", see mathworld.wolfram.com/Self-AvoidingWalk.html . – benh Apr 9 '14 at 15:27
Is oeis.org/A007764 what you want? – Gerry Myerson Apr 10 '14 at 11:06
I'm not convinced by your 3 by 3 grid giving 20 paths under restriction of moving up or right: I'd rather say 6 paths: – Wouter M. Apr 10 '14 at 19:46
UURR URUR URRU RRUU RURU RUUR and that's it. No? And oeis.org/A007764 contains a specific example for the non-intersecting rook paths as a(3)=12, not 210! (exclamation mark, not factorial). What's going on? – Wouter M. Apr 10 '14 at 19:55
@Wouter, you are moving from one square to another, Vincent is moving from one vertex to another. – Gerry Myerson Apr 11 '14 at 7:37