Thread: 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?

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

Could you explain a little more how you got that? I'm still new to Combinatorics.

Can you fill in the rest of the grid?

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

So the number of paths is just a permutation! Thanks Plato!

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 . Do you see why this is?

Yes, I understand it. I looked it up and realized permutation without repetition is something else. What I meant to say was that it was a permutation with redundant orderings removed. Is that correct?