How many possible ways to go right and up in an array Let's say we have a 2D matrix, and we begin at $(0, 0)$. 

We must travel $m$ steps to the right and $n$ steps up, in any order. Each step moves the position right or up by $1$.

For example if $n = 5$ and $m = 4$, the following would all be valid:

UP UP UP UP RIGHT RIGHT RIGHT RIGHT UP

RIGHT UP RIGHT UP RIGHT UP RIGHT UP RIGHT UP UP

UP UP RIGHT RIGHT UP RIGHT UP UP RIGHT


How many possible different ways are there to travel up $n$ times and right $m$ times, if the ordering in which we travel right or up does not matter, as long as we start at $(0, 0)$ and finish at $(n, m)$
You can treat this problem as a combinatorics problem: How many ways are there to reach from $(0,0)$ to $(m,n)$?.

Your steps are either $\mathit{up}$ denoted by $1$ for clarity, or $\mathit{right}$, denoted by $0$

No matter what path you take, you must move exactly $n$ times $up$ and exactly $m$ times $right$.

it means you would, in total, perform $m+n$ moves

Since any move is essentially either $1$ or $0$, it can be reduced to the following questions: Given a sequence of moves $P$ of length $m+n$, how many such options are there for such a $P$ in which #$1=n$, #$0=m$ ?

Solution:


  $$\binom{n+m}{n} = \binom{n+m}{m} $$