I was trying to solve the following problem related to "counting cases":

Consider the point $(0,0)$ in the plane and another point $(m,n)$ with $m,n>0$ integers. Suppose you want to get from the starting point $(0,0)$ to $(m,n)$ in unit steps, each step going upwards or to the right. Count the number of paths there exist to get from the initial point to $(m,n)$.

My attempt at a solution

To get to the point $m$ we have to move $m$ steps to the right and to get to the point $n$, $n$ steps upwards, so to get to $(m,n)$ we have to make a total of $m+n$ steps, $m$ to the right and $n$ upwards. Notice that there are different ways to do this task, for example, we can move first to the right $m$ steps and then when we are at $(m,0)$, we have to make $n$ steps upwards to get to $(m,n)$. Likewise, first we can get to the point $(0,n)$ by making $n$ steps upwards and then get to $(m,n)$ by advancing the $m$ remaining steps to the right.

It seems that up to some point, in each step you can choose "up" or "right", this stage at which you can't choose anymore would be when you are at a point of the form $(m,i)$ with $i<n$ or when you are at a point $(j,n)$ with $j<m$. I don't know how to translate this idea to a concrete numerical value, I would really appreciate if someone could help me.

  • 2
    $\begingroup$ Out of the $m + n$ steps, you have to choose $m$ steps in the right direction. In how many ways can you do this? $\endgroup$ – shardulc Apr 29 '16 at 4:36
  • 1
    $\begingroup$ Our path can be represented by an $m+n$-letter "word" made up of $m$ occurrences of the letter R (right) and $n$ occurrences of the letter U. How many such words are there? $\endgroup$ – André Nicolas Apr 29 '16 at 4:41
  • $\begingroup$ Thanks to both of you!, it was much more simpler than the way I was thinking about it: each number from $m+n$ represents the order of the step, from these, I have to choose $m$ in the right direction and of the remaining, $n$ upwards, so there are ${m+n \choose m}{m+n -m \choose n}={m+n \choose m}$ ways of doing this. $\endgroup$ – user156441 Apr 29 '16 at 4:45

Your Answer

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

Browse other questions tagged or ask your own question.