Routes with exceptions

Printable View

January 2nd 2013, 08:29 AM
KINGOLE

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!
January 2nd 2013, 09:00 AM
Plato

Re: Routes with exceptions

Quote:

Originally Posted by KINGOLE

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.
January 2nd 2013, 09:15 AM
KINGOLE

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 :)
January 2nd 2013, 09:45 AM
Plato

Re: Routes with exceptions

Quote:

Originally Posted by KINGOLE

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.
January 2nd 2013, 09:57 AM
KINGOLE

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.
January 2nd 2013, 10:27 AM
KINGOLE

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! :)

http://king-ole.com/images/p408q.png
January 2nd 2013, 12:52 PM
Plato

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.
January 2nd 2013, 12:56 PM
KINGOLE

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.
January 2nd 2013, 01:15 PM
Plato

Re: Routes with exceptions

Quote:

Originally Posted by kingole

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.
January 2nd 2013, 01:19 PM
KINGOLE

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.
January 2nd 2013, 01:24 PM
Plato

Re: Routes with exceptions

Quote:

Originally Posted by KINGOLE

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).
January 2nd 2013, 01:42 PM
KINGOLE

Re: Routes with exceptions

Oh, I get your previous example now.

The result I get using http://latex.codecogs.com/png.latex?...-\|AB\|-\|AC\| has to be subtracted from the total amount of routes from 0 to Z. :)

Here's my calculation:

http://king-ole.com/images/p408bad.png

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:

http://king-ole.com/images/p408ex2.png

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... (Thinking)

Thanks again for your help - I truly appreciate it.