Part 1: Understanding the Algorithm You are going to analyze a program that displays Pascal's triangle. This triangle is a sequence of integers that arises in numerous areas of math and computer science, especially combinatorics and probability. For example, the Pascal triangle of height 4 is: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 Entries in Pascal's triangle are indexed by integers. n is the number of the row and k is the position from the leftmost member of the row. The indexes in both directions start at zero (O), so in the last row listed above, C(4,0) = 1, C(4,1) = 4 and so on. n! The values themselves are computed by the formula C(n, k) which is called a k!(n-k)! combination. n! denotes a factorial, that is, the product n*(n-1)*(n-2)*...*2*1. The combinations can be interpreted as the number of ways to choose k elements from a collection containing n elements. When described, it is customary to say "n choose k", for instance '4 choose 2 is 6'. Let's look at this closer: If four objects are numbered 1 through 4, think of how many ways can you combine two of them. This is what "n choose k" calculated for us. 1. List all the possible pairings here. (Ex. {1, 2}, {2, 3}, ...) Keep in mind that the order of the numbers in a pairing does not matter - {1,2} is the same pairing as (2,1}. After you list all the pairings, compute C(4,2) by using the above formula. What is the result? Does it match the number of pairings you listed? (Hint: answer to the last question should be yes)