Do all parts!

A permutation of length n is a rearrangement of the numbers {1, 2, ellipsis n}. A permutation is called a mountain permutation if the numbers reading from left to right first increase and then decrease. For example, the permutation 1 2 3 5 7 6 4 is a mountain permutation of length 7, and 2 5 4 3 1 is a mountain permutation of length 5. We also consider increasing permutations of the form 1 2 3 ellipsis n and decreasing permutations of the form n ellipsis 3 2 1 to be mountain permutations. For example, 1 2 3 4 and 4 3 2 1 are mountain permutations of length 4 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 find a closed-form formula for M (n). 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? sigma_k=1^n (n - 1 k - 1) = 2^n-1 How many bits (0's and 1's) are required to represent a mountain permutation of length n? Simplify your answer. Describe how to encode a mountain permutation of length n using the number of bits you gave in part (c). How would you encode 2 5 7 6 4 3 1? Describe how to decode from a binary string to a mountain permutation of length n, if it has been encoded using the method you described in part (d) How would you decode 1 0 0 0 0 1