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

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 If we have three points

If we want to exclude any path through cannot pass through and any path through cannot pass through .

On the other hand, if we want to exclude we count paths to then from then from

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

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

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 it impossible for any path to pass through both of those points. So it is simple subtraction.

On the other hand, if it is possible for a path to pass through both of those points. So you must count the paths and subtract.

With three points you have more cases to consider.

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.

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!

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
So

The number of paths through at least one of A, B, or C is:
(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.

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.

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.



In the last term counts all paths thru all three:
which in this new case is possible.
You should four terms in that product.

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.

Originally Posted by KINGOLE

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

is (the number from 0 to A) times (the number from A to B) times (the number from B to Z).

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.