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 $\displaystyle (0,0)\text{ to }(10,10)$ If we have three points $\displaystyle A: (5,4),~B: (4,9),~\&~C: (2,3)$

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

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

Thus you must consider the placement of the points to include/exclude.

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

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 $\displaystyle 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 $\displaystyle 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 $\displaystyle O\to P\to Q\to Z$ and subtract.

With three points you have more cases to consider.

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.

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

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 $\displaystyle \|X\|$

So $\displaystyle \|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:

$\displaystyle \|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.

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.

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.

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

In the last term counts all paths thru all three:

$\displaystyle O\to a\to b\to c\to z$ which in this new case is possible.

You should four terms in that product.

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.

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?

$\displaystyle \|AB\|$ is (the number from 0 to A) times (the number from A to B) times (the number from B to Z).

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.