Calculating the number of possible paths through some squares

Solution 1:

The solution to the general problem is if you must take $X$ right steps, and $Y$ down steps then the number of routes is simply the ways of choosing where to take the down (or right) steps. i.e.

$$ \binom{X + Y}{X} = \binom{X + Y}{Y} $$

So in your example if you are traversing squares then there are 5 right steps and 1 down step so:

$$ \binom{6}{1} = \binom{6}{5} = 6 $$

If you are traversing edges then there are 6 right steps and 2 down steps so:

$$ \binom{8}{2} = \binom{8}{6} = 28 $$

Solution 2:

If you panic during the test, consider just drawing it as a Pascal's triangle

Where

• Value at the origin (x) is 1
• For all other nodes, the value is the sum of its top and left neighbors