# How many paths are there? [duplicate]

You have a 6 x 6 grid. You start at the top left corner and your "finish square" is the bottom right corner. You can only move to the right or move down. How many ways are there for you to get to the "finish square"?

• Similar PE problem. Mar 13 '16 at 11:16
• @Rubio Yeah it's not the end of the world, I just came across this question while browsing. And hey, fixing old problems from years ago is part of community curation :-) Good teamwork here. I'll delete my comments now. Mar 18 '20 at 16:47

Assuming that each "movement" moves me exactly one grid square, there are

252 possible paths.

Because

All paths will have 5 right moves and 5 down moves. Thus, this problem is equivalent to the permutations of RRRRRDDDDD, which is $$\frac{10!}{5!5!}=252$$.

## Alternative way of solving (that arrives at the same solution).

Since this puzzle is tagged "Visual" and not "Math," I'll provide a more visual solution as well. We will find how many paths there are from each square. The number of paths from the initial square is, of course, the solution.

To begin with, there is exactly one path from the goal to the goal (namely: you're already there!). Additionally, if you are already in the final row or column, there is only one path to the goal (follow that row or column to the end).

Our table so far looks like this:

?   ?   ?   ?   ?   1
?   ?   ?   ?   ?   1
?   ?   ?   ?   ?   1
?   ?   ?   ?   ?   1
?   ?   ?   ?   ?   1
1   1   1   1   1   1


Then, observe that for each of those question marks, since we can choose to move to either the space below us or to the right, each space has a number of paths equal to the sum of its two reachable neighbors. We can start by filling in a "2" in the one space whose neighbors we both know, and then work row by row and column by column.

252 126 56  21  6   1
126 70  35  15  5   1
56  35  20  10  4   1
21  15  10  6   3   1
6   5   4   3   2   1
1   1   1   1   1   1

• Mathematically, the visual proof is based on the fact that nCr + nC(r+1) = (n+1)C(r+1) Mar 13 '16 at 11:59
• If you look at it diagonally, it is actually like Pascal's Triangle. ( en.wikipedia.org/wiki/Pascal%27s_triangle )
– mbjb
Mar 13 '16 at 12:27
• The generalized solution for an NxN square is (2*N)!/(N!)^2, which can be found at OEIS #A000984. Mar 13 '16 at 15:11