0
$\begingroup$

Consider a rectangle whose length is m and whose height is n. A path from bottom left corner to top right corner is called valid, if in each step, it either goes one unit to the right or one unit upwards. if m = 5 and n = 3, how many valid paths are there?

This rectangle is basically a table with 15 cells(3 vertical x 5 horizontal). I need to find the total number of paths that I can take from bottom left corner to top right corner. I get the answer 16 paths. Can anyone verify this?

$\endgroup$
4
$\begingroup$

So you must go upwards $3$ times and rightwards $5$ times, in any order. It sounds to me like you need to make $8$ moves, and choose $5$ of them to be rightwards, the rest will be upwards, so you should get $$ \binom{8}{5}=\frac{8\cdot 7\cdot 6}{3\cdot 2\cdot 1}=56 $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That make sense, thanks! $\endgroup$ – user124659 Jan 29 '14 at 13:54
1
$\begingroup$

I think the best way to think problems like this is to think the route as a binary code. In this case 1=one unit upwards and 0=one unit right. So the binary code would look like for example 10011000. So 8 digits in total. And you can choose a place for the ones in $\binom{8}{3}=56$ ways. Note that $\binom{8}{3}=\binom{8}{5}$. Do you see why?

In general the code is $m+n$ digits long where $m=$ number of ones and $n=$ number of zeroes. So the route can be chosen in $\binom{m+n}{m}$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Your answer is incorrect.

Hint. For each valid path, write $a$ when you move right, and $b$ when you move up. An example of a valid path is then $$aababaab.$$

One way to solve the problem is first to characterize those "words" that correspond to valid paths, and then to count the number of such words by a combinatorial argument.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ok I think I got the answer. It's integer partitioning with three variables. So it's => x1+x2+x3=8 and the restriction is x1>=1,x2>=1,x3>=1. So the answer I think is => n-1 chooses k-1 which is 42. right? $\endgroup$ – user124659 Jan 29 '14 at 8:18
  • $\begingroup$ I made a mistake. It's weak restriction(x1>=0,x2>=0,x3>=0) because as long as they sum up to 8, it shouldn't matter. So, it's (n+k-1) chooses (k-1) $\endgroup$ – user124659 Jan 29 '14 at 8:29
  • $\begingroup$ The person who answered 56 was correct. How long is the word supposed to be, and how many $a$'s should it have? $\endgroup$ – user124636 Jan 29 '14 at 8:31

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.