In this exercise we will count the number of paths in the $xy$ plane between the origin $(0, 0)$ and point $(m, n),$ where $m$ and $n$ are nonnegative integers, such that each path is made up of a series of steps, where each step is a move one unit to the right or a move one unit upward. (No moves to the left or downward are allowed.) Two such paths from $(0, 0)$ to $(5, 3)$ are illustrated here.
- Show that each path of the type described can be represented by a bit string consisting of $m\: 0s$ and $n\: 1s,$ where a $0$ represents a move one unit to the right and a $1$ represents a move one unit upward.
- Conclude from part $(A)$ that there are $\binom{m + n}{n}$ paths of the desired type.
