# Counting all perpendicular paths crossing a grid

I'm new to Mathematica and thus don't really have any idea how to code what I need. My current research involves counting all possible paths that start at (0,0) and terminate at (n-1,n-1) on an n x n grid. The restriction is that any such paths cannot travel in the same direction twice in a row - e.g. a path that goes UP, RIGHT, RIGHT, UP on a 3x3 grid is invalid. I talked with a professor of mine about this but I'm still lost, even on the brute forcing methods, so I figured I would ask for help here. Thanks in advance!

• This is a problem in mathematics (combinatorics), and not the Mathematica programming language. – David G. Stork Feb 9 '17 at 22:12
• Yes, but I wish to enumerate small cases of this problem. – SAWblade Feb 9 '17 at 22:24
• @SAWblade You might be interested in GridGraph and FindPath then. I suspect that you will still have to figure out logic to exclude the unacceptable paths. – MarcoB Feb 9 '17 at 22:37
• It isn't clear whether you can only have UP and RIGHT as moves, or if LEFT and DOWN also work. You might find inspiration from the answers here – Jason B. Feb 9 '17 at 23:26
• assuming "RIGHT" and "UP" are the only allowed directions: maybe paths = {#, RotateRight@#} &@Flatten@Table[{"RIGHT", "UP"}, {n - 1}]? – kglr Feb 9 '17 at 23:30

ClearAll[f]
f[n_, dir : "UP" | "RIGHT" : "RIGHT"] := Module[{init=If[dir == "RIGHT", {1, 0}, {0, 1}]},
FoldList[Plus, {0, 0}, NestList[Reverse, init, 2 n - 3]]]


Examples:

f


{{0, 0}, {1, 0}, {1, 1}, {2, 1}, {2, 2}, {3, 2}, {3, 3}, {4, 3}, {4, 4}}

f[5, "UP"]


{{0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}, {3, 4}, {4, 4}}

Graphics:

n = 4;
Graphics[{Point[Tuples[Range[0, n], 2]], Red,  Line[f[n]], Blue, Line[f[n, "UP"]]}] Graphics[{MapIndexed[Text[Style[#2-1, 20], #]&, Outer[List, Range[0, n],Range[0, n]], {2}],
Red,  Line[f[n]], Blue, Line[f[n, "UP"]]}] 