In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging in an ordered fashion) objects or values. Informally, a permutation of a set of values is an arrangement of those values into a particular order. Thus there are six permutations of the set {1,2,3}, namely [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
In algebra and particularly in group theory, a permutation of a set S is defined as a bijection from S to itself (i.e., a map S → S for which every element of S occurs exactly once as image value). To such a map f is associated the rearrangement of S in which each element s takes the place of its image f(s). In combinatorics, a permutation of a finite set S is defined as an ordering of its elements into a list. In this sense, the permutations of S differ precisely by a rearrangement of their elements. For a set S that is given with an initial ordering, such as S={1,2,3,...,n}, these two meanings can be almost identified: applying a permutation in the first sense to this initial ordering gives an alternative ordering of the elements, which is a permutation in the second sense.
The term permutation is also used less formally to designate the act of rearranging parts of an object, or the result thereof. Thus one might define an anagram of a word as a permutation of its letters, or say that X^{3}Y+7+Y^{2}Z is (obtained by) a permutation of the terms of the polynomial X^{3}Y+Y^{2}Z+7. The act of permuting can also refer to substitution of symbols, for instance when saying that Y^{3}Z+Z^{2}X+7 is obtained from X^{3}Y+Y^{2}Z+7 by a (cyclic) permutation of the variables X, Y, Z. These statements can be given a precise meaning by considering an appropriate symmetric group action.
In combinatorics the second sense of "permutation" is sometimes broadened. In elementary combinatorics, the name "permutations and combinations" refers to two related problems, both counting possibilities to select k distinct elements from a set of n elements, where for kpermutations the order of selection is taken into account, but for kcombinations it is ignored. In fact counting kpermutations is used as a step towards counting the number of kcombinations, and also towards computing the number n! of permutations of the set (in either of the two meanings mentioned above). However kpermutations do not correspond to such permutations unless k = n, that is, unless the selection involves all available elements. In a different broadening of the notion of permutation, one can start, rather than with a set S, with a finite multiset M in which some values may occur more than once. A (multiset) permutation of M is a sequence of elements of M in which each of them occurs exactly as often as it occurs in M. Thus for M=[1,1,1,2,3,3], the sequence [3,1,2,1,1,3] is a multiset permutation of M, but [3,1,2,1,2,3,1] is not.
Permutations occur, in more or less prominent ways, in almost any domain of mathematics. They often arise when different orderings on certain finite sets are considered, possibly only because one wants to ignore such orderings and needs to know how many configurations are thus identified. For similar reasons permutations arise in the study of sorting algorithms in computer science. In algebra, an entire subject is dedicated to the detailed study of permutations, through the notion of symmetric group. The key to its structure is the possibility to compose permutations: by performing two given rearrangements in succession, the combination defines a third rearrangement.
Full article ▸
