What's the number of possible paths from $(0,0)$ to $(m,n)$ cell in a matrix?

Question

What's the number of paths from the $(0,0)$ cell to the $(m,n)$ cell in a matrix, where you can only turn right or down?

Answer 1

We have to choose $m$ right moves among $m+n$ or $n$ left moves among $m+n$ to determine a path, therefore

$$N=\binom{m+n}{m}=\binom{m+n}{n}=\frac{(m+n)!}{m!n!}$$

Refer also to the related

• Counting number of moves on a grid

Answer 2

In total, you have to make $m$ "right" moves and $n$ "down" moves. The total number of ways to arrive to $(m,n)$ is thus equal to the number of ways to arrange $m$ "right" moves and $n$ "down" moves, which is $$\frac{(m+n)!}{m!\,n!}\,.$$

The explanation is the following. First of all, for any collection of $k$ (distinguishable) objects, there are $k!$ ways to arrange them. How do we calculate the number of ways to arrange $m$ "right" moves and $n$ "down" moves from this? Well, let's start by noticing that there would be $(m!+n!)$ ways to arrange them if each move was distinguishable from the others (for example, if making a certain "down" move first and then another "down" move would be different from making the latter first and the former next—which of course doesn't make sense). So we need to "uncount" the arrangements where moves of the same type have been switched around amongst them.

The way to do that is to divide $(m+n)!$ by $m!$ and by $n!$, since $m!$ and by $n!$ are, respectively, the number of ways to arrange $m$ "right" moves and the number of ways to arrange $n$ "down" moves amongst themselves.

Answer 3

If you want to get from $(0,0)$ to $(m,n)$ only performing $r$ and $d$ movements a typical path would look like $\underbrace{r,r,r, \cdots , r}_{m \text{ times}} + \underbrace{d,d,d, \cdots , d}_{n \text{ times}}$.

Note that regardless how to shuffle the $r$ and $d$ movements in the end you will always get to $(m,n)$. The only thing left to calculate is in how many ways you can choose $m$ (or $n$) elements out of $(n+m)$. In other words:

$$\binom{m+n}{n} \text{ or } \binom{m+n}{m}$$