Number of Paths from O(0,0) to A(7,8) - No (3,4)

[Lilia]

Homework Statement

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)

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

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.

 

[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.

 

[haruspex]

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.

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?

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.

I believe Lilia has taken that into account already.

 

[Ray Vickson]

Homework Statement

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)

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

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.

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

 

[Lilia]

For Q2, how many ways are there from (0,0) to (7,8) altogether?

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.

 

[HallsofIvy]

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.

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

 

[haruspex]

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

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.

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?

Yes.

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

Looks right.

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)

Yes.

 

[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?

 

[haruspex]

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?

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.

 

[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?

 

[Samy_A]

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?

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

 

[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?

 

[Samy_A]

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?

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