Results 1 to 8 of 8

Math Help - Number of Paths

  1. #1
    Newbie Vulcan's Avatar
    Joined
    Mar 2008
    Posts
    8

    Number of Paths

    Imagine a 5X4 grid:

    * * * * * <--B
    * * C * *
    * * * * *
    A-->* * * * *




    The bottom left corner is A, the top right B. How many ways are there to get from A to B? Also, how many ways are there to get to B that cross through point C?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2008
    Posts
    148
    Label each point with the number of paths to get to that point.

    Are we only allowed to travel east and north (right and up)? Presumably this is the case since otherwise the answer is infinitely many paths.

    Now along the bottom edge there are all 1's since you can only get to each point by a move right from the previous point, same with the left edge.

    Continue to fill in the grid. (HINT: the number of paths to a point p is the sum of the number of paths to the two points which can lead to p)

    If you must pass through point C just break the problem into 2 subproblems, the number of paths from A to C and the number of paths from C to B. With that information what is the total number of paths from A to B that pass through C?


    An interesting class of such problems requires the grid to be a square and asks for the number of paths from A to B that don't cross the diagonal (stay in the lower triangular half of the square).
    Last edited by iknowone; March 28th 2008 at 10:08 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie Vulcan's Avatar
    Joined
    Mar 2008
    Posts
    8

    Please elaborate

    Could you explain a little more how you got that? I'm still new to Combinatorics.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2008
    Posts
    148
    Can you fill in the rest of the grid?
    Attached Thumbnails Attached Thumbnails Number of Paths-comb1.bmp  
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1613
    Awards
    1
    For anyone to go from A to B, making steady progress, has to move 4 blocks east and 3 blocks north.
    One path is EEEENNN. Any rearrangement of that string represents a path.
    NENEENE means first go north then east then north then two blocks east then north and finally east to arrive at B.
    There are \frac{{\left( {7!} \right)}}{{\left( {4!} \right)\left( {3!} \right)}} ways to rearrange that string and each rearrangement represents a path from A to B.
    How many from A to C? How many from C to B? Now multiply those two.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie Vulcan's Avatar
    Joined
    Mar 2008
    Posts
    8
    So the number of paths is just a permutation! Thanks Plato!
    Last edited by Vulcan; March 29th 2008 at 09:17 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1613
    Awards
    1
    Quote Originally Posted by Vulcan View Post
    So the number of paths is just a permutation without repetition!
    No that is not correct.
    Do you understand how to find the number of ways to rearrange the word “Tallahassee”?
    It is \frac {11!}{(3!)(2!)^3}. Do you see why this is?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie Vulcan's Avatar
    Joined
    Mar 2008
    Posts
    8
    Yes, I understand it. I looked it up and realized permutation without repetition is something else. What I meant to say was that it was a permutation with redundant orderings removed. Is that correct?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of paths
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2010, 12:07 PM
  2. Number of Paths
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 30th 2010, 06:07 AM
  3. Finding the number of paths...
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 18th 2010, 05:02 PM
  4. How many paths...?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 14th 2008, 07:54 AM
  5. Counting Paths
    Posted in the Statistics Forum
    Replies: 6
    Last Post: October 14th 2007, 11:44 PM

Search Tags


/mathhelpforum @mathhelpforum