Find a Path

Consider a grid that is $16$ meters long and $14$ meters wide and stand at the lower left corner. Given that you can move only up and right in single meter increments, how many ways can you get to the top right corner?

This is essentially the same problem as the one posted above, because the amount of ways to get to a given point $(x,y)$ on the grid is the sum of the ways to get to the point below it $(x, y-1)$ and the number of ways to get to point to the left of it $(x-1, y)$ . Thus, $A(x,y)=\left(\begin{array}{c}x+y\\ x\end{array}\right)$ or identically, $\left(\begin{array}{c}x+y\\ y\end{array}\right)$ and $A(16, 14) = \left(\begin{array}{c}30\\ 14\end{array}\right)=145422675$ .

Alternatively, one could prove that $A(x,y)=\left(\begin{array}{c}x+y\\ x\end{array}\right)$ by induction.

From the first few positive integer values of $x$ and $y$ , it appears that $A(x,y) = \dbinom {x+y}y$ . The following prove that it is so.

$\begin{aligned} A(x,y) & = A(x-1,y) + A(x,y-1) & \small \color{#3D99F6} \text{If } A(x,y) = \binom {x+y}y \ \forall \ x, y \in \mathbb Z^+ \\ & = \binom {x+y-1}y + \binom {x+y-1}{y-1} \\ & = \frac {(x+y-1)!}{y!(x-1)!} + \frac {(x+y-1)!}{(y-1)!x!} \\ & = \frac {(x+y)(x+y-1)!}{x!y!} \\ & = \frac {(x+y)!}{x!y!} \\ & = \binom {x+y}y & \small \color{#3D99F6} \text{QED} \end{aligned}$

Therefore, $A(16,14) = \dbinom {30}{14} = \boxed{145422675}$ .