Question 173
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 \lt n \text{ and } 0 \leq y \lt 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!}$.
$$
\left\{(x, y) \in \mathbb{Z}^2 \mid 0 \leq x \lt n \text{ and } 0 \leq y \lt 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!}$.