1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – астон вілла олоф мэллбэрг Mar 26 '17 at 5:33
  • $\begingroup$ Do you mean $m$ rows and $n$ columns or $m$ horizontal and $n$ vertical line segments? $\endgroup$ – N. F. Taussig Mar 26 '17 at 10:22
1
$\begingroup$

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: 1] 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!}$$

A more comprehensive explanation is given here:
https://betterexplained.com/articles/navigate-a-grid-using-combinations-and-permutations/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.