Browse · MATH
Printjmc
counting and probability senior
Problem
Moving only south and east along the line segments, how many paths are there from to ? 
Solution
First, put the two missing segments in and count the number of paths from to on the complete grid. Each path from to consists of a sequence of 12 steps, three of which are ``down'' and nine of which are ``right.'' There are ways to arrange 3 D's and 9 R's, so there are 220 paths from to .
Now we will count the number of paths that go through one of the forbidden segments. No path goes through both of them, so we may count the number of paths that go through each segment and sum the results. Define and as shown in the figure. There are 5 ways to get from to and 6 ways to get from to . So there are ways to get from to through the first forbidden segment. Similarly, there are 30 ways to get from to through the second forbidden segment. So the total number of paths from to on the original grid is .
Now we will count the number of paths that go through one of the forbidden segments. No path goes through both of them, so we may count the number of paths that go through each segment and sum the results. Define and as shown in the figure. There are 5 ways to get from to and 6 ways to get from to . So there are ways to get from to through the first forbidden segment. Similarly, there are 30 ways to get from to through the second forbidden segment. So the total number of paths from to on the original grid is .
Final answer
160