In this problem we fix a positive integer n and consider the set S(n), which contains...

Transcribed Image Text:

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...nºn, 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 1º2k3⁰.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...nºn equals n! 1c1c₁!2c2c₂! nºn cn!' (Hint: For a permutation π = a₁a2an 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.) 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...nºn, 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 1º2k3⁰.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...nºn equals n! 1c1c₁!2c2c₂! nºn cn!' (Hint: For a permutation π = a₁a2an 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.)