Paths on a grid and how many

550 Views Asked by At

You start at coordinate (0, 0) on a grid and want to reach position (3, 3). On this grid, you can only move right or up, not diagonally. How many paths are there?

This is a question I am trying to solve - would the answer to this be 20? I have done this graphically, writing out all the different ways this journey could be done and arrive at 20 - however, is there a simpler way to calculate this, with a formula?

1

There are 1 best solutions below

10
On

The number of ways to get to $(a, b)$ is equal to the number of ways to get to $(a-1, b)$ plus the number of ways to get to $(a, b-1)$.

Draw a grid and place the number $1$ at the origin. That's because there is exactly one way to reach the origin.

Now take the points $(0, 1)$ and $(1, 0)$ and write how many ways you can get to each of the points. Then take $(0, 2), (1, 1)$ and $(2, 0)$ and see how many ways you can get there. Then take $(0, 3), (1, 2), (2, 1)$ and $(3, 0)$. And so on. You should get your answer within a minute or so. No need for formulas, although there is one, and it's rather simple.

Bonus: If you stand at the point $(4, 4)$ and look at your grid as you draw it, can you recognize the process? That's where the formula comes from.