# Number of Paths

• March 27th 2008, 07:02 PM
Vulcan
Number 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?
• March 28th 2008, 07:59 AM
iknowone
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).
• March 28th 2008, 10:10 AM
Vulcan
Could you explain a little more how you got that? I'm still new to Combinatorics.
• March 28th 2008, 10:21 AM
iknowone
Can you fill in the rest of the grid?
• March 28th 2008, 11:13 AM
Plato
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 $\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.
• March 29th 2008, 09:06 AM
Vulcan
So the number of paths is just a permutation! Thanks Plato!(Bow)
• March 29th 2008, 09:17 AM
Plato
Quote:

Originally Posted by Vulcan
So the number of paths is just a permutation without repetition!

No that is not correct.
Do you understand how to find the number of ways to rearrange the word “Tallahassee”?
It is $\frac {11!}{(3!)(2!)^3}$. Do you see why this is?
• March 29th 2008, 10:37 AM
Vulcan
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?