Sam has to go to work from home. Sam moves either SOUTH or EAST when going to work. How many distinct routes are there for sam to go to work?

Question

The following figure depicts the paths from home to work. SAM never travels through the park when going to work.

Answer 1

He has to pass through exactly one of E, F, and C. If he passes through E or C then there's trivially only one path (for each) he can take. If he passes through F, there are $\binom{2}{1} = 2$ ways he can get from A to F and $\binom{3}{2} = 3$ ways he can get from F to K, for a total of $2\times 3 = 6$. So in all there are $1+1+6 = 8$ ways he can get home.

Answer 2

Write the number of possibilities of reaching a vertex $X$ from $A$. It starts like $A:1$ as getting to $A$ is unique, both $B$ and $D$ also have only $1$ possibilities. They simply add up, for example the possibilities to arrive at $I$ are the possibilities arriving at either to $H$ or to $G$ (plus the unique $GI$ path, resp. $HI$ path). $$A:1,\ B:1,\ D:1,\ F:2,\ E:1,\ G:3,\ H:2,\ I:5,\ C:1,\ J:3,\ K:8 $$

Answer 3

If the park were not there, there would be ${3+2 \choose 2}=10$ possible paths.

Adding the park cuts off one possible line segment Sam could walk along (from the $BC$ midpoint to $H$). There is only one way he could get to the top of that line segment, and $2$ possible continuances once he reaches $H$. So the total number of paths that don't go through the park is $10 - 1 \cdot 2 = 8$.