# Combinatorics: How many ways can an $m \times n$ board be traversed from the top left to the bottom right by moving only to the right and down?

I have a $m \times n$ board, and I can only move right and down. Say you start from the top left, how many ways can you go to the bottom right?

This is a classical dynamic programming question, with dp [i][j] = dp[i-1][j] + dp[i][j-1]. And you initialize the top row and the left-most column to be 1.

I am wondering what would be the mathematical approach in solving this problem?

• Can you try doing an argument by induction? try extending the row/column by one and see how the answer changes. For base cases, consider only one row or column. – астон вілла олоф мэллбэрг Mar 26 '17 at 5:33
• Do you mean $m$ rows and $n$ columns or $m$ horizontal and $n$ vertical line segments? – N. F. Taussig Mar 26 '17 at 10:22

One approach would be to classify moves down and right as $\mathsf D$ and $\mathsf R$ respectively. Then, given a $m\times n$ grid, to get from the top left to the bottom right, you would have to move downwards $m$ times, and move right $n$ times, in some kind of order.
For example, consider a $5\times 3$ grid. One possible route would be: Or, written like this: $\mathsf{DDDDDRRR}$
Now, the problem becomes a simple matter of sequence permutation, which is a very elementary concept. The number of ways the sequence $\mathsf{DDDDDRRR}$ can be ordered (which is just another way of saying the number of different ways you can get from the top left corner to the bottom right corner) is: $$\frac{8!}{5!\times 3!} = 56$$
To generalize, for a $m\times n$ grid, the number of ways to get from the top left corner to the bottom right corner is given by:
$$\frac{(m+n)!}{m!\times n!}$$