# Math Help - Upright path problem

1. ## Upright path problem

An upright path problem is one in which you have to figure out how many paths there are from one point to another and you can only move up and right on the coordinate system. Here is my problem:
How many paths from (0,0) to (6,6) never cross the line y=x?
Can anyone give me some guidance?

2. Originally Posted by chiefbutz
An upright path problem is one in which you have to figure out how many paths there are from one point to another and you can only move up and right on the coordinate system. Here is my problem:

Can anyone give me some guidance?
I've come up with a theory for how to solve it.

Each dot has two places it can go to (with a few exceptions that only have one). So that dot's total number of options will be the sum of the total number of options from each of the two places it can go. So, for example, the entire right row will only have 1 option (to go up) Then starting at the next row (remember to start at the point (5,5) since you cannot cross that line. (5,5) can only go to the right, so it is the sum of 1, and has 1 option. The dot below it can go up or right, so it is the sum of 1 and 1 = 2. The next will be 2+1=3, and so on. When you get to the origin, you should have the sum of the total number of paths unless I messed up. Then you multiply it by two, because it is two triangles.

I'll work on a diagram.

Note that this may be wrong, but I think it will work.

edit: I attached my unverified solution. For one triangle, there are 132 possibilities, so for the whole thing, there are 264 possibilities.

3. Here is another approach to this problem.

4. I know the way TPH linked to, but I am having troubles on figuring out how to convert that to this problem. So I have to use that method but do it one column at a time and then add them all up?

Oh and angel.while for the whole thing there are 924 solutions.

Would dividing 924 in half get me the answer? It doesn't seem like it should, but basic intuition says it would...

5. The numbers you want are called Catalan Numbers: Catalan_numbers
$C_n = \frac{{{2n} \choose n}}{{n + 1}}$
Here are a few $C_6 = 132$. So the first response is correct and that is the total.