HMMT 2006 T2

For this problem, our lawn is an $m \times n$ rectangular grid of clumps, that is, with $m$ rows running east-west and $n$ columns running north-south. To be even more explicit, we might say our clumps are at the lattice points

$$\left\{(x, y) \in \mathbb{Z}^{2} \mid 0 \leq x<n \text { and } 0 \leq y<m\right\}$$

However, mobots are now allowed to be oriented to go either north or east only. So one allowable formation for $m=2, n=3$ might be as follows:

$$\begin{array}{lll} \cdot & \rightarrow \\ \uparrow & \rightarrow & . \end{array}$$

Prove that the number of allowable formations for given $m$ and $n$ is $\frac{(m+n)!}{m!n!}$.