348,315 views
15 votes
15 votes
You are to move from A to B, always moving

right or down along the lines. On how many
different paths can you go? [The number of paths
from A to various intersections has been included.

You are to move from A to B, always moving right or down along the lines. On how many-example-1
User Beejee
by
3.0k points

1 Answer

29 votes
29 votes

Answer:

70

Explanation:

You want the number of paths from corner to corner on a 5×5 grid with no backtracking.

Pascal's triangle

The geometry of the problem matches that of Pascal's triangle, attached.

In the attached figure, the value at each node is the sum of the values above and to the left. This matches the counting process for paths that can be used to get to any particular point on the grid: the total number of ways to get there is the sum of the ways it can be approached from above and the ways it can be approached from the left.

The given grid has some numbers filled in. If we continue to assign values to nodes that are the sum of the values above and to the left, we find the node values match the upper left 5×5 array of values in the attachment.

The value at the lower right corner of that array is 70. That is, ...

there are 70 ways to get from A to B.

__

Alternate solution

The path taken will always have 8 steps. Of those, 4 must be to the right, and 4 must be down. The number of ways we can choose 4 of those 8 steps to be steps to the right is "8 choose 4" ...

C(8,4) = 8!/(4!(8-4)!) = (8·7·6·5)/(4·3·2·1) = 70

Of course, using Pascal's triangle is simply another way to find the value of C(n,k).

You are to move from A to B, always moving right or down along the lines. On how many-example-1
User Tauren
by
2.8k points