2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 :) $\endgroup$ – Jean-Claude Arbaut Mar 26 '16 at 18:14
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

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