3. Linda lives in a neighborhood where the streets either go North and South or East and West, forming rectangular blocks. All the streets go all the way through the neighborhood. Linda lives 3 blocks South and 4 blocks West of her school. She enjoys a little diversity in her life, and so she tries to take a different route to school each day. How many different routes can she take which involve moving only North or East?
This is an example of a problem where solving all of the simpler problems will enable us to see the pattern which will let us get the solution.
To get to any point on the southernmost or westernmost streets, there is only 1 way to go: straight down the street. If she ever turns East or North, she can never get back, according to these rules. Given any other corner, there are two ways to get to that corner. She either has to come from the corner to the East or the corner to the South. So the number of ways to get to any of those corners will be the sum of the number of ways she could have gotten to the corner to the West plus the number of ways she could have gotten to the corner to the South. With this scheme, we can start from Linda's house and fill in the number of ways to get to each corner - all the way to school.
When we do this we see the numbers in Pascal's triangle appearing at the corners. The number that appears at the school is either C(7,3) or C(7, 4) depending on how you make the correspondence between the numbers on the blocks and the numbers in Pascal's triangle. Fortunately both of these numbers are
To answer the question of why Pascal's triangle comes into play, first consider a question about which Linda is probably wondering: of all these routes, which is the shortest? If you have rectangular blocks, since the opposite sides of a rectangle are equal in length, it doesn't matter whether you go around the block to the left or the right, it is the same distance either way. As a result, all of the routes are the same length: 3 blocks North and 4 blocks East. What distinguishes the different routes is which of the 7 blocks she goes East, and which of the 7 blocks she goes North. The blocks where she travels North is a 3 element subset of the set of 7 blocks that she walks. As a result, there are as many different routes as there are 3 element subsets of a 7 element set. If instead of considering the northbound blocks, we considered the eastbound blocks we would conclude that there are as many different routes as there are 4 element subsets of a 7 element set.