What are the possible routes from A to D in a 2D grid?

[cronuscronus]

Hi all.

I have a grid with 4 points, A, B, C, and D.
Each valid move is either going to the right for one block or going down for 1 block.

Here is the grid.

I need to calculate the following:
a) How many different valid routes from A to D?
b) How many valid routes from A to D that must avoid B?
c) How many valid routes from A to D that must pass through Both B and C?
d) How many valid routes from A to D that must pass through B but must avoid C ?

I believe for A, I would calculate 13 choose 9 to obtain 715 possible routes.

Where I am confused is how I calculate in the avoidance and musts. For example, on b, if I wanted to avoid B, would I treat A to be like a mini 4x5 sub-grid? Would I subtract 4 choose 4 from 715 to obtain 710 possible routes?

Any help is appreciated. I can't seem to find any information on this in my book :(.

 

[LCKurtz]

Hi all.

I have a grid with 4 points, A, B, C, and D.
Each valid move is either going to the right for one block or going down for 1 block.

Here is the grid.

I need to calculate the following:
a) How many different valid routes from A to D?
b) How many valid routes from A to D that must avoid B?
c) How many valid routes from A to D that must pass through Both B and C?
d) How many valid routes from A to D that must pass through B but must avoid C ?

I believe for A, I would calculate 13 choose 9 to obtain 715 possible routes.

Where I am confused is how I calculate in the avoidance and musts. For example, on b, if I wanted to avoid B, would I treat A to be like a mini 4x5 sub-grid? Would I subtract 4 choose 4 from 715 to obtain 710 possible routes?

Any help is appreciated. I can't seem to find any information on this in my book :(.

That isn't correct for A. It is going to take $13+9=22$ steps to get from A to D. Each step is either r or d for "right" or "down". So think of 22 blank spaces that are going to be either r or d depending whether that step is right or down. You have to choose which slots correspond to the 13 down steps. How many ways can you do that? Alternatively, how many ways can you choose which slots are move right? That might get you started.

 

[cronuscronus]

Right. But the question is how many valid routes there are, not how many steps.

The other method I saw to count this would be (9+13)! / 9!13! which equals 497,420. I have no idea if it's 715 or 497,420.

 

[LCKurtz]

You need to give a bit more thought to what I said. If I tell you exactly which steps will be down, does that completely determine a route?

 

[cronuscronus]

Unfortunately it doesn't make any sense to me.

What do you mean by "choose which slots correspond to the 13 down steps"? How do I go about "choosing" that?

If there are 13 down steps, and 9 right steps, I suppose that there are 13x9 choices? I really have no idea, sorry.

 

[LCKurtz]

Do you see that you have to take 22 steps to get from A to D? And that 13 of them have to be down? And that once you pick which of the 22 steps are down, the rest have to be to the right? So that once you know which steps are to be down, there is only 1 path that does that?

 

[cronuscronus]

Yes, I do see that, but I don't understand how that helps me count the total number of routes. If I choose a route by hand, that's just 1 route. There has to be some kind of formula, otherwise I'd be here for a week calculating routes.

 

[LCKurtz]

Here's one route:

dddddddddddddrrrrrrrrr

If I put the d's in different spots will that give me a different route?

 

[cronuscronus]

I took some time to relax and I've come back to the problem now.
So if we look at having 13 moves down, and 9 moves right, then we can get the combinations using 13C9.

a) 13C9 = 715 possible routes.

b)
If we want to avoid B, we should find out how many moves from A to B.
5C4 = 5, and 715 -5 = 710. So there are 710 possible routes while avoiding B.

c) For the routes which must pass through B and C, we look at the number of steps to reach B, and the number of steps to reach C, and then the number of steps to reach D from C.
So we get
5C4 + 7C9 + 9C5 = 138 possible routes.

Am I on the right track now?

 

[LCKurtz]

Here's one route:

dddddddddddddrrrrrrrrr

If I put the d's in different spots will that give me a different route?

I took some time to relax and I've come back to the problem now.
So if we look at having 13 moves down, and 9 moves right, then we can get the combinations using 13C9.

a) 13C9 = 715 possible routes.

No. I told you that was wrong with my first post. And you ignored my last post, which I re-quoted above. I'm trying to lead you to discover how to do it. Answer the above question.

 

[cronuscronus]

I'm not ignoring anything. I honestly don't understand.

I'm trying. Yes. If you put d's in the different spots you will get a different route.

I think my nCk is incorrect. So if we have 22 moves, and I want to see how many down moves I have, I would choose 13 from 22, so 13C22, which is 497,420 paths. Is this on the right track?

 

[cronuscronus]

When I calculate the routes from A to B, I do it with 9choose5, which equals 125. This is the same formula for 22choose13 which yields 497,420 from A to D.

497,420 - 3128 = 491,254 routes avoiding B.

For c, the valid routes from A to D that must pass through both B and C, I just add the routes up.

9choose5 + 9choose6 + 8choose5 = 125+84+56 = 265 routes.

For d, the valid routes from A to D which pass through B but avoid C, I add the routes from A to B (125), subtract the routes from B to C (84), and add the routes from B to D (3128).
125-84+3128 = 3169 routes.

I think I'm getting there, slowly?

 

[LCKurtz]

I'm not ignoring anything. I honestly don't understand.

I'm trying. Yes. If you put d's in the different spots you will get a different route.

I think my nCk is incorrect. So if we have 22 moves, and I want to see how many down moves I have, I would choose 13 from 22, so 13C22, which is 497,420 paths. Is this on the right track?

That isn't "how many down moves you have". It is how many ways you can choose which moves to be down. $_{22}C_{13} = 497420$ is correct. Do you understand my first post now?

 

[cronuscronus]

I do. Thanks. I am going to go over the other problems again tonight.

I would assume I can treat the area from A to B, or B to C as a "sub-grid" and calculate the choices within those sub-grids.

Thanks again.

 

[LCKurtz]

When I calculate the routes from A to B, I do it with 9choose5, which equals 125. This is the same formula for 22choose13 which yields 497,420 from A to D.

Wrong numbers for A to B. Look again.

497,420 - 3128 = 491,254 routes avoiding B.

For c, the valid routes from A to D that must pass through both B and C, I just add the routes up.

9choose5 + 9choose6 + 8choose5 = 125+84+56 = 265 routes.

For d, the valid routes from A to D which pass through B but avoid C, I add the routes from A to B (125), subtract the routes from B to C (84), and add the routes from B to D (3128).
125-84+3128 = 3169 routes.

I think I'm getting there, slowly?

Very slowly. Pretty much all wrong. You have (a) correct, now let's get (b) correct. On part at a time. To answer (b) you need to know how many routes from A to D go through B so you can leave them out. How can you calculate that?

 

[cronuscronus]

To calculate the number of routes that go through B. I believe I want to determine how many moves I need to make down and right to get from A to B.

To get from A to B, I see I need to go down 3 at some point, and right 5 at some point. So there are 8choose3 (or 56) routes from A to B.

So would I remove 56 from 497420?

 

[LCKurtz]

Wrong numbers for A to B. Look again.



Very slowly. Pretty much all wrong. You have (a) correct, now let's get (b) correct. On part at a time. To answer (b) you need to know how many routes from A to D go through B so you can leave them out. How can you calculate that?

To calculate the number of routes that go through B. I believe I want to determine how many moves I need to make down and right to get from A to B.

To get from A to B, I see I need to go down 3 at some point, and right 5 at some point. So there are 8choose3 (or 56) routes from A to B.

Wrong numbers. Look at your grid again. Second time I've pointed that out to you.

So would I remove 56 from 497420?

No. Read my re-quoted post again.

 

[cronuscronus]

You said "It is how many ways you can choose which moves to be down. 22C13=497420 is correct." Above. I'm not sure why you're saying that's wrong now?

Can you throw me a bone here man instead of just saying "wrong wrong wrong"? It's not helping. Trust me. I read your posts over and over agian.

The B is in the upper left hand corner of the grid. It is 3 down, and 5 right. No?

 

[LCKurtz]

You said "It is how many ways you can choose which moves to be down. 22C13=497420 is correct." Above. I'm not sure why you're saying that's wrong now?

Can you throw me a bone here man instead of just saying "wrong wrong wrong"? It's not helping. Trust me. I read your posts over and over agian.

The B is in the upper left hand corner of the grid. It is 3 down, and 5 right. No?

Maybe we are looking at different pictures? If you start at the upper left corner it is 3 steps down and 4 steps right to get to corner B isn't it?

 

[cronuscronus]

Yes. Ok I see now. It is 3 down and 4 right.

So is it correct to say 7choose3, and the result is 35? If so, I will take some time to try and re-work the rest of the problems.

Thanks agian.

 

[LCKurtz]

That is the correct number of paths from A to B. So next is to figure how many paths from A to D through B.

 

[cronuscronus]

But we want to avoid B for part b, correct? So I would think we want to calculate the number of routes from A to D, and just subtract the routes from A to B?

 

[LCKurtz]

No, because for every route from A to B there are lots of routes from B to D. You have to subtract the total number of routes from A to D through B.

 

[cronuscronus]

I see. This is because we could technically go right a bunch from A, then straight down. This makes sense.

So if we want to calculate A to D, through B, we could calculate the number of routes from A to B, which is 35.

Next we could calculate the number of routes from B to D.
To do this I see 11 down, 6 right. So the number of routes is 17choose11, or 12,376.

So if we have 497,420 routes from A to D, and (35 + 12376) through B.

497420 - (35+12376) = 485,009 routes avoiding B.

What do you think?

 

[LCKurtz]

I see. This is because we could technically go right a bunch from A, then straight down. This makes sense.

So if we want to calculate A to D, through B, we could calculate the number of routes from A to B, which is 35.

Next we could calculate the number of routes from B to D.
To do this I see 11 down, 6 right. So the number of routes is 17choose11, or 12,376.

You are still having problems counting the steps. I don't understand why.

So if we have 497,420 routes from A to D, and (35 + 12376) through B.

What do you think?

Think about that with smaller numbers. If I can get from A to B in 2 ways and B to D in 3 ways, are there only 3+2=5 paths from A to D? Draw a little picture and count them.

 

[cronuscronus]

Let's try and find out why I can't count this.

If I am on A, and I go down 3, and right 4, then I am on B. After I go down 3, I count that same cell as 1 for the right. So I am in column 4, not column 5 (if it is 1-indexed) no?

 

[LCKurtz]

Put your pen on corner B. Move it one step at a time downward to the bottom, counting the steps. How many do you get? Now how many steps to the right to get to D?

 

[cronuscronus]

10 down, 5 right. I feel like an idiot now.

 

[cronuscronus]

You are still having problems counting the steps. I don't understand why.



Think about that with smaller numbers. If I can get from A to B in 2 ways and B to D in 3 ways, are there only 3+2=5 paths from A to D? Draw a little picture and count them.

So I drew this out, and you're correct. You would want to multiply, not add. So if we could get from A to B in 2 ways, and B to D in 3 ways, there are 6 paths from A to D.

 

[LCKurtz]

So I drew this out, and you're correct. You would want to multiply, not add. So if we could get from A to B in 2 ways, and B to D in 3 ways, there are 6 paths from A to D.

OK. So now you should be ready to give the correct calculations to answer (b).

 

[cronuscronus]

Thanks for sticking with me.

So, A to D is 497420 options.
A to B is 35 options.
B to D is 10 down, 5 right. 15choose5 = 3003.

Now we want to know how many routes through B, so we can "avoid" that.

The routes through B is (35 * 3003). Which equals 105,105.

So, 497420-105105 = 392,315 possible routes from A to D while avoiding B.

 

[LCKurtz]

Thanks for sticking with me.

So, A to D is 497420 options.
A to B is 35 options.
B to D is 10 down, 5 right. 15choose5 = 3003.

Now we want to know how many routes through B, so we can "avoid" that.

The routes through B is (35 * 3003). Which equals 105,105.

So, 497420-105105 = 392,315 possible routes from A to D while avoiding B.

Ok. That's good. Now, using the concepts you have used so far, see if you can do (c) and (d). I won't be back to this thread until later today or maybe tomorrow.

 

[cronuscronus]

Thanks again for the help.

For c, we want to know how many routes pass through both B and C.
I think this is more straight forward. Can simply multiply our way through this.
A to B is 35.
For B to C, we have 5 down, and 2 right required to get to C. So, we can calculate 7choose2, which equals 21.
For C to D, we have 5 down, and 3 right required to get to D. So we can calculate 8choose3, which equals 56.

So, 35*21*56 = 41,160 routes going through B and C.

For d we want to know how many routes must go through B, and must avoid C.
Here are our steps to each point:
A to B = 35
B to C = 21
C to D = 56
A to C is 8 down, 6 across. 14choose8 = 3003 (interesting).
B to D is also 3003
I would compute 35*3003 - 21*3003 = 42,042 routes which must pass through B and avoid C.

 

[cronuscronus]

I think part d has an error.

We need to calculate (A to B * B to D) - (B to C * C to D), which equals
(35*3003) - (21*56)
105105 - 1176 = 103,929

 

[LCKurtz]

Thanks again for the help.

For c, we want to know how many routes pass through both B and C.
I think this is more straight forward. Can simply multiply our way through this.
A to B is 35.
For B to C, we have 5 down, and 2 right required to get to C. So, we can calculate 7choose2, which equals 21.
For C to D, we have 5 down, and 3 right required to get to D. So we can calculate 8choose3, which equals 56.

So, 35*21*56 = 41,160 routes going through B and C.

Correct.