permutatio

Permutatio, from the Latin permutare meaning to change the order, is the concept of rearranging elements of a set. In mathematics, a permutation of a finite set A is a bijection from A to itself, equivalently an arrangement of the elements in a particular order. The set of all permutations of a set with n elements forms the symmetric group S_n under composition.

If the elements are distinct, the number of permutations is n!, the factorial of n. If some elements are indistinguishable, the number of distinct arrangements of a multiset with multiplicities m1, m2, ..., mk is n! divided by the product of the factorials of the multiplicities. For example, the permutations of {a, b, c} are six: abc, acb, bac, bca, cab, cba. For a multiset {a, a, b}, there are 3!/2! = 3 distinct permutations: aab, aba, baa.

Permutations can be expressed as products of disjoint cycles; the identity permutation leaves all elements fixed. The parity of a permutation is even or odd, depending on whether it can be written as an even or odd number of transpositions. The permutation group S_n consists of all permutations of an n-element set, with composition as the operation, and it plays a central role in abstract algebra.

Applications include counting problems in combinatorics, ordering tasks, sorting algorithms, cryptography, and the study of symmetries in science. The concept has roots in early combinatorics and is central to the development of group theory.