group A transposition is a permutation which exchanges two elements and keeps all others fixed; for example (1 3) is a transposition. Every permutation can be written as a product of transpositions; for instance, the permutation g from above can be written as g = (1 2)(2 5)(3 4). Since g can be written as a product of an odd number of transpositions, it is then called an odd permutation, whereas f is an even permutation. The representation of a permutation as a product of transpositions is not unique; however, the number of transpositions needed to represent a given permutation is either always even or always odd. There are several short proofs of the invariance of this parity of a permutation. The product of two even permutations is even, the product of two odd permutations is even, and all other products are odd. Thus we can define the sign of a permutation: With this definition, is a group homomorphism ({+1, −1} is a group under multiplication, where +1 is e, the neutral element). The kernel of this homomorphism, that is, the set of all even permutations, is called the alternating group An. It is a normal subgroup of Sn, and for it has elements. The group Sn is the semidirect product of An and any subgroup generated by a single transposition. Furthermore, every permutation can be written as a product of adjacent transpositions, that is, transpositions of the form . For instance, the permutation g from above can also be written as . The sorting algorithm bubble sort is an application of this fact. The representation of a permutation as a product of adjacent transpositions is also not unique. Cycles A cycle of length k is a permutation f for which there exists an element x in {1, ..., n} such that x, f(x), f2(x), ..., fk(x) = x are the only elements moved by f; it is required that since with the element x itself would not be moved either. The permutation h defined by is a cycle of length three, since , and , leaving 2 and 5 untouched. We denote such a cycle by , but it could equally well be written or by starting at a different point. The order of a cycle is equal to its length. Cycles of length two are transpositions. Two cycles are disjoint if they have disjoint subsets of elements. Disjoint