Results 1 to 5 of 5

Math Help - Upright path problem

  1. #1
    Newbie
    Joined
    Jan 2008
    Posts
    9

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by chiefbutz View Post
    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.
    Attached Thumbnails Attached Thumbnails Upright path problem-paths.jpg  
    Last edited by angel.white; January 27th 2008 at 01:19 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Here is another approach to this problem.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2008
    Posts
    9
    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...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Path fitting problem - which approach?
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: May 10th 2010, 02:21 PM
  2. Multi-Agent Path Planning Optimization Problem.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 14th 2010, 04:08 AM
  3. degree of a path, path homotopy.
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 19th 2009, 06:37 PM
  4. need help on path and vector field problem
    Posted in the Calculus Forum
    Replies: 6
    Last Post: December 19th 2008, 09:11 AM
  5. Convex hull and shortest path problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 19th 2007, 12:45 PM

Search Tags


/mathhelpforum @mathhelpforum