# 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. Feb 9, 2017 at 22:12
• Yes, but I wish to enumerate small cases of this problem. Feb 9, 2017 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. Feb 9, 2017 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 Feb 9, 2017 at 23:26
• assuming "RIGHT" and "UP" are the only allowed directions: maybe paths = {#, RotateRight@#} &@Flatten@Table[{"RIGHT", "UP"}, {n - 1}]?
– kglr
Feb 9, 2017 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"]]}] 