) (Optional - Easy) Let M(n) be the number of mountain permutations of length n. Write a recurrence relation that M(n) satisfies, then solve the recurrence to show that the closed-form formula for M(n) is M(n) = 2n1 . (b) (8 points) Prove the following identity by interpreting it combinatorially in the context of mountain permutations. That is, what is each side counting in terms of mountain permutations, and why are those the same? Xn k=1 n 1 k 1 = 2n1 Hint: Let k represent the position of the largest element, n, in the permutation. (c) (2 points) How many bits (0s and 1s) are required to represent a mountain permutation of length n? Simplify your answer. (d) (5 points) Describe how to encode a mountain permutation of length n using the number of bits you gave in part (c). Illustrate your description with an example. (e) (5 points) Describe how to decode a mountain permutation of length n, if it has been encoded using the method you described in part (d). Illustrate your description with an example.

4. Recall from Problem 1 of Homework 2 that a list of n distinct integers a1, a2,... ,an is called a mountain list if the elements reading from left to right first increase and then decrease A permutation is called a mountain permutation if the numbers, when reading from left to right, form a mountain list. For example, the permutation 1235764 is a mountain permutation of length 7, and 25431 is a mountain permutation of length ;5 We also consider increasing permutations of the form 123...n and d of the form n...321 to be mountain permutations. For example, 1234 and 4321 are mountain permutations of length 4 permutations (a) (Optional - Easy) Let M(n) be the number of mountain permutations of length n. Write a recurrence relation that M(n) satisfies, then solve the recurrence to show that the closed-form formula for M(n) is M(n) 2-1 (b) (8 points) Prove the following identity by interpreting it combinatorially in the context of mountain permutations. That is, what is each side counting in terms of mountain permutations, and why are those the same? = 2n k-1 (c) (2 points) How many bits (0's and 1's) are required to represent a mountain permutation (d) (5 points) Describe how to encode a mountain permutation of length n using the number (e) (5 points) Describe how to decode a mountain permutation of length n, if it has been Hint: Let k represent the position of the largest element, n, in the permutation. of length n? Simplify your answer of bits you gave in part (c). Illustrate your description with an example encoded using the method you described in part (d). llustrate your description with an example