Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
    
You are right of course: $m$ points, $m-1$ intervals, even a child knows that! I removed the answer. Not worth correcting, since it would amount to yours, which is nice. And +1 :) – Jean-Claude Arbaut Mar 26 at 18:14

There are $m$ points in a row and $n$ points in a column. Hence any horizontal line is connected by $m-1$ horizontal steps and any vertical line by $n-1$ vertical steps.

We can clearly see a bijection between paths for reaching the top with the arrangement of $m-1$ horizontal steps and $n-1$ vertical steps.

Hence the total number of paths reaching the top is same as finding the number of arrangements of $m-1$ horizontal steps and $n-1$ vertical steps, which is nothing but $\frac{(m-1 +n-1)!}{(m-1)!(n-1)!}$

share|cite|improve this answer

A path is obtained by specifying in some order $m-1$ arrows that go in one direction and $n-1$ arrows that go in another direction. Thus we must shuffle $m-1$ say zeros and $n-1$ ones. Can you count how many permutations the multiset $\{0^{m-1},1^{n-1}\}$ admits? Well, we can mindlessly shuffle the $m+n-2$ symbols in $(m+n-2)!$ ways, but since there are $m-1$ repetitions of zero and $n-1$ repetitions of one, we must divide by $(m-1)!(n-1)!$ to account for such repetitions, leaving $$\binom{m+n-2}{m-1,n-1}$$ premutations.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.