Results 1 to 12 of 12

Math Help - Routes with exceptions

  1. #1
    Newbie KINGOLE's Avatar
    Joined
    Jan 2013
    From
    Texas
    Posts
    7

    Routes with exceptions

    As part of a problem I'm trying to solve, I have to find the number of routes from (0,0) to (X,Y) only going up or to the right (both X and Y are positive integers).

    I am using central binomial coefficient to find the routes, which is working great.

    R = (X+Y)! / (X!*Y!)

    If there's ONE point I cannot go through (A,B), I can find the total number of valid routes this way:

    routes(0,0,X,Y) - (routes(0,0,A,B) * routes(A,B,X,Y))

    That also works fine.

    However, when I add another point I cannot go through (C,D), I am unsure what to subtract from what, and so on, as some routes go through A,B but not C,D, some through C,D but not A,B, and some through both.

    Of course, what I'm trying to get to is a bunch of points I can't go through, but once I can understand 2 points, I think I can figure the rest out.

    Any help is greatly appreciated.

    Thanks!
    Last edited by KINGOLE; January 2nd 2013 at 09:37 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,964
    Thanks
    1784
    Awards
    1

    Re: Routes with exceptions

    Quote Originally Posted by KINGOLE View Post
    As part of a problem I'm trying to solve, I have to find the number of routes from (0,0) to (X,Y) only going up or to the right (both X and Y are positive integers).
    Of course, what I'm trying to get to is a bunch of points I can't go through, but once I can understand 2 points, I think I can figure the rest out.

    There are some additional cases. Suppose we are going from (0,0)\text{ to }(10,10) If we have three points A: (5,4),~B: (4,9),~\&~C: (2,3)

    If we want to exclude A~\&~B any path through A cannot pass through B and any path through B cannot pass through A.

    On the other hand, if we want to exclude A~\&~C we count paths to C then from C\text{ to }A then from A\text{ to }(10,10).

    Thus you must consider the placement of the points to include/exclude.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie KINGOLE's Avatar
    Joined
    Jan 2013
    From
    Texas
    Posts
    7

    Re: Routes with exceptions

    Thanks for your comment Plato, but I'm not sure you understand my problem completely.

    First of all, A comes before B, as I can only more UP or RIGHT, so I can never move from a higher number to a lower one.

    So on my way to Z (10,10), I must NOT go through A, B nor C.

    Therefore, A would be (2,3), B (4,9) and C (5,4), and finally Z (10,10).

    From (0,0) to Z, I can go through A only, B only, C only, A and B, A and C, B and C, or none of A, B or C.

    So, I am looking for a way to subtract routes from routes so it gives me all routes from (0,0) to Z where I do not go through any of A, B or C.

    If there was only the point A (2,3), the result would be:

    From (0,0) to (10,10) = 184,756
    From (0,0) to (2,3) = 10
    From (2,3) to (10,10) = 6,435
    Total routes to avoid (10 x 6,435) = 64,350
    Total good routes (184,756-64,350) = 120,406

    Thanks
    Last edited by KINGOLE; January 2nd 2013 at 10:21 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,964
    Thanks
    1784
    Awards
    1

    Re: Routes with exceptions

    Quote Originally Posted by KINGOLE View Post
    Thanks for your comment Plato, but I'm not sure you understand my problem completely.
    I assure you that I understand your problem completely.
    You did not understand the reply.

    If E: (3,7)~\&~F: (6,2) it impossible for any path to pass through both of those points. So it is simple subtraction.

    On the other hand, if P: (3,2)~\&~Q: (6,7) it is possible for a path to pass through both of those points. So you must count the paths O\to P\to Q\to Z and subtract.

    With three points you have more cases to consider.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie KINGOLE's Avatar
    Joined
    Jan 2013
    From
    Texas
    Posts
    7

    Re: Routes with exceptions

    Thanks!

    But what I can't picture in my head, is how to count the paths I need to subtract:

    If I count O -> P -> Q -> Z only, what about the ones that goes through only P and those that goes through only Q?

    If we use the previous example (0,0) to (10,10):

    Total routes = 184,756

    Routes through P (3,2) = 64,350

    Routes through Q (6,7) = 60,060

    Routes from P to Q = 56

    That would mean that 56 of the routes through P also goes through Q, and 56 of the routes through Q also goes through P.

    So I guess that means that those 56 routes are counted twice and must be subtracted.

    Would it be correct to assume that the number of valid routes would then be: 184,756 - (64,350 + 60,060) + 56 = 60,402?

    Thanks.

    EDIT: No! that's not correct either.

    I just ran a small code that shows the result as 79,946, so I'm a bit lost atm.
    Last edited by KINGOLE; January 2nd 2013 at 11:11 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie KINGOLE's Avatar
    Joined
    Jan 2013
    From
    Texas
    Posts
    7

    Re: Routes with exceptions

    Okay, did some tests in Excel, and found the way to avoid 2 points P and Q on the route.

    184,756 = A→D

    64,350 = A→B→D

    60,060 = A→C→D

    19,600 = A→B→C→D

    79,946 = (A→D) - (A→B→D) - (A→C→D) + (A→B→C→D)

    Now I "just" need to completely understand why that is, and test it with 3 points.

    EDIT: Okay, 3 points threw me off again. Need to do more thinking... Any help will be greatly appreciated!

    Last edited by KINGOLE; January 2nd 2013 at 12:18 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,964
    Thanks
    1784
    Awards
    1

    Re: Routes with exceptions

    I will work this one out for you.
    A would be (2,3), B (4,9) and C (5,4), and finally Z (10,10).
    We want to avoid those three points.
    The number of paths through X is denoted by \|X\|
    So \|A\|=\frac{5!}{2!\cdot 3!}\cdot\frac{15!}{8!\cdot 7!}

    The number of paths through at least one of A, B, or C is:
    \|A\|+\|B\|+\|C\|-\|AB\|-\|AC\| (note there are no paths thru both B&C). Subtract that from the total to get the number of paths thru none of those points.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie KINGOLE's Avatar
    Joined
    Jan 2013
    From
    Texas
    Posts
    7

    Re: Routes with exceptions

    Thanks Plato, very much appreciated.

    What would that look like if there could be a path through all three (A,B,C) = A(2,3), B(5,5), C(6,7), and Z(10,10)?

    If I can grasp that, I should be able to understand n points where n > 3 as well.

    Thanks.
    Last edited by KINGOLE; January 2nd 2013 at 02:19 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,964
    Thanks
    1784
    Awards
    1

    Re: Routes with exceptions

    Quote Originally Posted by kingole View Post
    what would that look like if there could be a path through all three (a,b,c) = a(2,3), b(5,5), c(6,7), and z(10,10)?
    This is known as inclusion/exclusion. It counts the number of paths thru at least one of a, b, or c.

    \|a\|+\|b\|+\|c\|-\|ab\|-\|ac\|-\|bc\|+\|abc\|

    In the last term counts all paths thru all three:
    O\to a\to b\to c\to z which in this new case is possible.
    You should four terms in that product.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie KINGOLE's Avatar
    Joined
    Jan 2013
    From
    Texas
    Posts
    7

    Re: Routes with exceptions

    I can't get your first example to give me the correct number (77,629).

    When you say ||AB|| do you mean ||A|| x ||B|| or (0,0) -> A -> B -> Z?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,964
    Thanks
    1784
    Awards
    1

    Re: Routes with exceptions

    Quote Originally Posted by KINGOLE View Post
    When you say ||AB|| do you mean ||A|| x ||B|| or (0,0) -> A -> B -> Z?
    \|AB\| is (the number from 0 to A) times (the number from A to B) times (the number from B to Z).
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie KINGOLE's Avatar
    Joined
    Jan 2013
    From
    Texas
    Posts
    7

    Re: Routes with exceptions

    Oh, I get your previous example now.

    The result I get using has to be subtracted from the total amount of routes from 0 to Z.

    Here's my calculation:



    Thank you so much for your help.

    I will try the same with your last example, and see if I get it.

    EDIT: Did the one where all points could be passed in one go, and it came out correctly to 62,502:



    Now I need to test with more points.

    My hope is that if I have 6 points (A,B,C,D,E,F) and the possible combinations are (0,A,B,F,Z), (0,B,C,D,F), and (0,A,D,Z) to have the result:

    ||0Z|| - ||A|| + ||B|| + ||C|| + ||D|| + ||E|| + ||F|| - ||0ABFZ|| - ||0BCDF|| - ||0ADZ||

    but I have a feeling it's not going to be that easy...

    Thanks again for your help - I truly appreciate it.
    Last edited by KINGOLE; January 2nd 2013 at 05:37 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Differentiate with routes
    Posted in the Calculus Forum
    Replies: 2
    Last Post: February 23rd 2011, 11:40 AM
  2. Probability problem involving routes.
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 27th 2010, 05:41 PM
  3. choosing possible routes home
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: May 8th 2010, 04:23 PM
  4. Squares and routes
    Posted in the Algebra Forum
    Replies: 6
    Last Post: January 8th 2010, 01:42 PM
  5. Number of routes
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 11th 2009, 02:53 PM

Search Tags


/mathhelpforum @mathhelpforum