Homework Help: Routes through a 2D grid.

1. Nov 17, 2013

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 :(.

2. Nov 17, 2013

LCKurtz

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.

3. Nov 17, 2013

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.

4. Nov 17, 2013

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?

5. Nov 17, 2013

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.

6. Nov 17, 2013

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?

7. Nov 17, 2013

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.

8. Nov 17, 2013

LCKurtz

Here's one route:

dddddddddddddrrrrrrrrr

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

9. Nov 17, 2013

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?

10. Nov 17, 2013

LCKurtz

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.

11. Nov 17, 2013

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?

12. Nov 18, 2013

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?

13. Nov 18, 2013

LCKurtz

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?

14. Nov 18, 2013

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.

15. Nov 18, 2013

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?

16. Nov 18, 2013

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?

17. Nov 18, 2013

LCKurtz

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

No. Read my re-quoted post again.

18. Nov 18, 2013

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?

19. Nov 18, 2013

LCKurtz

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?

20. Nov 18, 2013

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.

21. Nov 18, 2013

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.

22. Nov 18, 2013

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?

23. Nov 18, 2013

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.

24. Nov 18, 2013

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?

25. Nov 18, 2013

LCKurtz

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.