2. Let Fp(n, k) denote the number of permutations of {1,...,n} having exactly k fixed points, for n > 0 and k > 0. Fp(0,0) is 1 (there is exactly one permutation of the empty set, and it doesn't have any fixed points), and Fp(n,k) is clearly 0 if k > n. n a. What is Fp(n,k)? k=0 A benevolent spirit points out to you that a permutation on n elements with exactly k fixed points consists of (1) a choice of k elements to be fixed points followed by (2) a permutation of the remaining elements having zero fixed points. b. Convince yourself of the truth of the preceding sentence. c. Use this to formulate a recurrence relation for Fp(n, k) and tabulate the values of Fp(n, k) for n and k values from 0 up to 5. (Hint: You'll probably find that Fp(n,0) can't be computed directly from your recurrence. But you should know what the total in each row needs to be. So work out Fp(n, k) for all the k > 0 entries in row n first, and then subtract to get the k = 0 entry.) d. Briefly explain the values you find for Fp(n,n - 1) (not just what they are, but a good reason why they are what they are.) 2. Let Fp(n, k) denote the number of permutations of {1,...,n} having exactly k fixed points, for n > 0 and k > 0. Fp(0,0) is 1 (there is exactly one permutation of the empty set, and it doesn't have any fixed points), and Fp(n,k) is clearly 0 if k > n. n a. What is Fp(n,k)? k=0 A benevolent spirit points out to you that a permutation on n elements with exactly k fixed points consists of (1) a choice of k elements to be fixed points followed by (2) a permutation of the remaining elements having zero fixed points. b. Convince yourself of the truth of the preceding sentence. c. Use this to formulate a recurrence relation for Fp(n, k) and tabulate the values of Fp(n, k) for n and k values from 0 up to 5. (Hint: You'll probably find that Fp(n,0) can't be computed directly from your recurrence. But you should know what the total in each row needs to be. So work out Fp(n, k) for all the k > 0 entries in row n first, and then subtract to get the k = 0 entry.) d. Briefly explain the values you find for Fp(n,n - 1) (not just what they are, but a good reason why they are what they are.)