Permutaation

Permutaation is a rearrangement of the elements of a set. In mathematics, a permutation of a finite set with n elements is a bijection from the set to itself, or equivalently an arrangement of its elements in a sequence of length n with no repetition. For the standard set {1,2,...,n}, a permutation records the order in which these elements appear.

The collection of all permutations of n elements is called the symmetric group S_n, and under composition it forms a group. The number of distinct permutations of n elements is n!, the factorial of n.

Every permutation can be decomposed uniquely into disjoint cycles, and this cycle form provides a compact description of how elements move. The parity of a permutation—the property of being even or odd—is invariant and equals the parity of the number of transpositions needed to express it. A permutation has an inverse, which is also a permutation, and the product of a permutation and its inverse is the identity.

Common ways to write permutations include one-line notation (pi(1) pi(2) ... pi(n)) and cycle notation (a1 a2 ... ak). For example, in S_3 the six permutations can be written as the identity, the transpositions (12), (13), (23), and the two 3-cycles (123) and (132).

Applications of permutation theory appear in sorting and data arrangement, shuffle algorithms, cryptography, coding theory, and the study of genome rearrangements. Related ideas include derangements (permutations with no fixed points) and permutation groups, which support many areas of algebra and discrete mathematics.