## Different Paths

We must travel from $A$ to $B$ along the lines shown. If we only allow movement upward or to the right, how many different paths are there from $A$ to $B$?

Source: NCTM Mathematics Teacher, December 2005

SOLUTION

If we fill in the entire $4\times 4$ grid including the top left corner, the bottom right corner and the center, a path from $A$ to $B$ would take $4$ steps upward and $4$ steps to the right. How many different paths from $A$ to $B$ is given by how many ways can we choose $4$ steps to the right out of $8$ steps?
$\dbinom{8}{4}=70$
We need to subtract from $70$ the number of paths that go through the $3$ points in the top left corner, the $3$ points of the right bottom corner, and the central point of the grid. With a little patience and a pencil and paper, we find out that $8$ paths go through the top left corner; $8$ paths through the right bottom corner; $18$ paths through the central point from the left hand point $C$; and $18$ paths through the central point from the bottom point $D$.

Number of different paths from $A$ to $B$ equals
$70-8-8-18-18=18$

Answer: $18$

Alternative solution
We collapse the empty central square and thus obtain a $3\times 3$ grid as follows

A path from $A$ to $B$ would take $6$ steps $3$ of which are upward and $3$ to the right. How many ways can we choose $3$ steps to the right out of $6$ steps is given by
$\dbinom{6}{3}=20$
We subtract the paths going through $C$ and $D$ and obtain
$20-1-1=18$