In this problem we fix a positive integer n and consider the set S(n), which contains all permutations of length n. (a) A permutation that consists of one cycle only is called a cyclic permutation. Prove that there are (n 1)! cyclic permutations in S(n). (b) Assume n = 2k is even. A permutation that consists of k 2-cycles is called an fixed-point free involution. Prove that the number of fixed-point free involutions in S(n) is 1.3.5... (2k-1). (c) Define the type of o E S(n) to be the formal expression 101202...nn, where c; is the number of cycles in o of length i. For example, a cyclic permutation has type 102... (n 1)n, and a fixed-point free involution has type 12k3.n, (where k = n/2 and n is even). 7 Note that we always have =1 ici = n. Show that the number of o E S(n) with a given type c = 101202...nn equals n! 1c1c!2c2c! nn cn!' (Hint: For a permutation = aa2an in word notation, parenthesize the word so that the first c cycles have length 1, the next c cycles have length 2, and so on. This gives a map from all permutation to permutations with cycle type c. For each permutation in the image, count how many preimages it has.)