Imagine a 5X4 grid:

* * * * * <--B

* * C * *

* * * * *

A-->* * * * *

The bottom left corner is A, the top right B. How many ways are there to get from A to B? Also, how many ways are there to get to B that cross through point C?

Printable View

- Mar 27th 2008, 07:02 PMVulcanNumber of Paths
Imagine a 5X4 grid:

* * * * * <--B

* * C * *

* * * * *

A-->* * * * *

The bottom left corner is A, the top right B. How many ways are there to get from A to B? Also, how many ways are there to get to B that cross through point C? - Mar 28th 2008, 07:59 AMiknowone
Label each point with the number of paths to get to that point.

Are we only allowed to travel east and north (right and up)? Presumably this is the case since otherwise the answer is infinitely many paths.

Now along the bottom edge there are all 1's since you can only get to each point by a move right from the previous point, same with the left edge.

Continue to fill in the grid. (HINT: the number of paths to a point**p**is the sum of the number of paths to the two points which can lead to**p**)

If you must pass through point**C**just break the problem into 2 subproblems, the number of paths from**A**to**C**and the number of paths from**C**to**B**. With that information what is the total number of paths from**A**to**B**that pass through**C**?

An interesting class of such problems requires the grid to be a square and asks for the number of paths from A to B that don't cross the diagonal (stay in the lower triangular half of the square). - Mar 28th 2008, 10:10 AMVulcanPlease elaborate
Could you explain a little more how you got that? I'm still new to Combinatorics.

- Mar 28th 2008, 10:21 AMiknowone
Can you fill in the rest of the grid?

- Mar 28th 2008, 11:13 AMPlato
For anyone to go from A to B, making steady progress, has to move 4 blocks east and 3 blocks north.

One path is EEEENNN. Any rearrangement of that string represents a path.

NENEENE means first go north then east then north then two blocks east then north and finally east to arrive at B.

There are $\displaystyle \frac{{\left( {7!} \right)}}{{\left( {4!} \right)\left( {3!} \right)}} $ ways to rearrange that string and each rearrangement represents a path from A to B.

How many from A to C? How many from C to B? Now multiply those two. - Mar 29th 2008, 09:06 AMVulcan
So the number of paths is just a permutation! Thanks Plato!(Bow)

- Mar 29th 2008, 09:17 AMPlato
- Mar 29th 2008, 10:37 AMVulcan
Yes, I understand it. I looked it up and realized permutation without repetition is something else. (Doh) What I meant to say was that it was a permutation with redundant orderings removed. Is that correct?