Problem 5 (4+8+4 = 16 points). (a) Alfred lives at the Northwest corner of a 4 x 4 square grid (in the yellow square). He works at the southeast corner of the grid (in the green square). To get to work, he my pass through any of the intermediate squares, but he can only ever move to the south and to the east. Two example routes. Fill in each square of the grid with the number of paths to work that pass Alfred can take from the yellow square to get to that square. (Note that this is not the number of paths that pass through the square on his way to work.) (b) Replace each number in each square with an expression of the form (2). Explain why can we easily represent the number of paths between two squares as a choose function. That is, what is the set being chosen from, and what are we choosing, to get the value for each square. (c) Pascal's Triangle is a structure that shows up across mathematics, from counting to algebra to proba- bility. To construct Pascal's Triangle, we start with an infinitely tall pyramid of squares. The square at the top contains a 1, and any square on the left or right edge contains a 1. Any other square contains the sum of the numbers in the squares directly above it. 1 11 12 1 1 3 3 1 14641 What is the relationship between the paths in parts (a) and (b) and Pascal's Triangle? Counting the rows of Pascal's Triangle from top to bottom, and counting within a row from left to right, what is the kth value of the nth row of Pascal's Triangle? (To make it easier, you should start both counts at 0.)