# Paths in a grid

Tags:
1. Dec 26, 2015

### Lilia

1. The problem statement, all variables and given/known data
In a grid O(0,0) A(7,8) find the number of paths that
1. pass through (3,4)
2. don't pass through (3,4)
3. pass through M(2,3) AND N(4,6)
4. DON'T pass pass through M(2,3) and N(4,6)
5. pass through ONLY ONE of M(2,3) and N(4,6)
6. pass through AT LEAST ONE of M(2,3) and N(4,6)
7. pass through M(2,3) and don't pass through N(4,6)

2. Relevant equations
If the grid starts at O(0,0) and ends at A(7,8) then the length of each path is 7+8=15. The number of paths is C(7+8,7) = C(15,7)

3. The attempt at a solution
To find the number of paths that pass through (3,4), I found
1. the number of paths from O(0,0) to M(3,4) which is C(3+4,3) = C(7,3) = 7*6*5 / 1*2*3 = 35
2. the number of paths from M(3,4) to A(7,8) which is C(4+4,4) = C(8,4) = 8*7*6*5 / 1*2*3*4 = 70
3. 35*70=2450

This one is easy so I figured it out easily, please provide me with some guidance to solve the others too.

2. Dec 26, 2015

### theodoros.mihos

To move (0,0) $\to$ (7,8) trough (3,4) you must add all possible ways moving only to "right" and "up".
Because this condition may possible ways are less than you think.

3. Dec 26, 2015

### haruspex

Q3 is just more of the same - (0,0) to (2,3), then (2,3) to (4,6) etc.
For Q2, how many ways are there from (0,0) to (7,8) altogether?
I believe Lilia has taken that into account already.

4. Dec 27, 2015

### Ray Vickson

One hint only: in (2), number of paths from (0,0) to (7,8) NOT passing through (3,4) = total paths from (0,0) to (7,8), minus those that pass through (3,4).

5. Dec 27, 2015

### Lilia

There are C(7+8,7) = C(15,7) = 15*14*13*12*11*10*9 / 1*2*3*4*5*6*7 = 6435 paths from O(0,0) to A(7,8). If I exclude the number of paths through M(3,4), that'd be number of paths that don't pass through M(3,4), right?

Q3: C(5,2) * C(5,2) * C(5,2). Isn't there anything to add?

Q5 and Q7 are similar in a way. In Q5 it says ONLY ONE which is, the path passes through M(2,3) and doesn't pass through N(4,6) OR the path passes through N(4,6) and doesn't pass through M(2,3). Therefore, for Q7

the number of paths that pass through M(2,3) is C(5,2)*C(10,5),
don't pass through N(4,6) is C(15,7) - (10,4)*C(5,2) (all minus those passing through N(4,6)),
multiplication of these results will be the number of paths that pass through M(2,3) and don't pass through N(4,6)

Edit: the number of paths that pass through (2,3) and don't pass through (4,6) will be the number of paths through (2,3) minus the number of paths through (2,3) AND (4,6)

This is what I figured out so far. Please tell me where I go wrong.

Last edited: Dec 27, 2015
6. Dec 27, 2015

### HallsofIvy

The original post said nothing about only moving "right and up". Why are you adding that condition?

7. Dec 27, 2015

### haruspex

True, but the calculation performed there for Q1 appears to assume that anyway, so post #2 is redundant.. Some condition must be applied to make the answer finite.
Yes.
Looks right.
Yes.

8. Dec 28, 2015

### Lilia

And for Q6 (through AT LEAST one) it will be all paths minus those paths that don't pass trough M(2,3) and N(4,6), i.e.

C(15,7) - [ C(15,7) - [C(5,2)*C(10,5)+C(9,3)*C(6,2)] + C(5,2)*C(4,1)*C(6,2) ]

Is this right?

9. Dec 28, 2015

### haruspex

I'm not following how you get that expression. As a numeric answer (if I've computed yours correctly) I get a little more.
You might be getting confused between two interpretations of 'and'. English is not great for expressing logical conjunctions. In Q4, 'and' means both. In your rephrasing of Q6 above, it has to mean either.
I would start with the number that pass through the one point, the number that pass through the other point, then consider how many paths are double counted if I add them.

10. Dec 28, 2015

### Lilia

So, to get the correct answer, from all the paths I should exclude the number of paths that pass through (2,3), then exclude the number of paths that pass through (4,6), then exclude the number of paths that pass through both of the points?

11. Dec 28, 2015

### Samy_A

Since you have to count the paths that pass through at least one of the points (2,3) and (4,6), you cannot exclude paths that pass through these points.

As haruspex suggested:
- get the number of all the paths that pass through (2,3)
- get the number of all the paths that pass through (4,6)
If you add these two numbers, you have counted all the paths that you need for Q6. But, again as haruspex wrote, some path have been counted twice. If you can identify these paths and get that number ...

12. Dec 29, 2015

### Lilia

The number of all the paths that pass through (2,3) + the number of all the paths that pass through (4,6) - the number of all the paths that pass through (2,3) and (4,6), right?

13. Dec 29, 2015

### Samy_A

Yes, that is what I meant. That should give the answer to Q6.