Let denote the group of permutations of a finite set . Show that every permutation can be written as a product of disjoint cycles. Explain briefly why two permutations in are conjugate if and only if, when they are written as the product of disjoint cycles, they have the same number of cycles of length for each possible value of .
Let denote the number of disjoint cycles, including 1-cycles, required when is written as a product of disjoint cycles. Let be a transposition in and any permutation in . Prove that .