# How many valid paths are there?(counting problem)

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?

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

• That make sense, thanks! – user124659 Jan 29 '14 at 13:54

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

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.$$
• The person who answered 56 was correct. How long is the word supposed to be, and how many $a$'s should it have? – user124636 Jan 29 '14 at 8:31