[Math] A problem in combinatorics, counting number of different paths on a grid of points

combinationscombinatorics

in my combinatorics class I was asked the question on counting different paths in a grid on which I need help:

We suppose we are on a grid of points with m points in each row and n points in each column and we are presently at the bottom left corner point, and we define a step as moving one point to the right or one point upwards. We take these steps in order to go from the initial point (bottom left corner) to the upper right corner point. We are asked to find the number of different paths that achieve this.

I am not so good at combinatorics but figured it has something to do with enumeration problems but I could not find this as a reference problem anyway and I cannot solve it. Therefore, I truly need help on this so I wrote it here in the hopes of someone presenting me the solution. I thank all helpers.

Best Answer

In all cases you need exactly $m+n-2$ steps, and a path is an ordered $m+n-2$-tuple of symbols, either "up" or "right". Exactly $n-1$ steps must be "up" and exactly $m-1$ must be "right" and a paths are in bijective correspondence with all the ordered $m+n-2$-tuples of symbols with exactly the right number of "up" symbols and "right" symbols.

So the answer is ${m+n-2}\choose {m-1}$