Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

enter image description here

share|improve this question
4  
This is called "self-avoiding rook walk", see mathworld.wolfram.com/Self-AvoidingWalk.html . –  benh Apr 9 at 15:27
    
Is oeis.org/A007764 what you want? –  Gerry Myerson Apr 10 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 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 at 19:55
    
@Wouter, you are moving from one square to another, Vincent is moving from one vertex to another. –  Gerry Myerson Apr 11 at 7:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.