0
$\begingroup$

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)$

$\endgroup$
  • 1
    $\begingroup$ What have you tried so far? It may be difficult to think about this starting at (0,0). If we're at cell (n,m) how many ways can we move up or right? Clearly this is 1 (because there is only 1 way to not move). If we're at cell (n-1,m) how many ways can we move up or right? Again, clearly this is 1. Similar for (n, m-1). Now, consider we're at cell (n-1,m-1). How can we combine our solutions from (n-1,m) and (n,m-1) to determine a solution to (n-1,m-1)? This is a common dynamic programming formulation. $\endgroup$ – ryan Apr 18 at 3:05
  • $\begingroup$ @ryan you might want to make that into an answer $\endgroup$ – Pål GD Apr 18 at 7:02
  • 1
    $\begingroup$ @ryan Dynamic programming is not needed. There are nine moves to be made, four of which are RIGHT. Thus simple combinatorics will solve the question. $\endgroup$ – Hendrik Jan Apr 18 at 8:10
  • $\begingroup$ @HendrikJan yes combinatorics will get it, but I feel the DP formulation gives more intuition behind it in my opinion. I could've also just linked here. The DP formulation is also just Pascal's Triangle in grid form. $\endgroup$ – ryan Apr 18 at 16:12
2
$\begingroup$

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} $$

$\endgroup$

Your Answer

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