Permutation

related topics
{math, number, function}
{math, energy, light}
{style, bgcolor, rowspan}

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 SS 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 X3Y+7+Y2Z is (obtained by) a permutation of the terms of the polynomial X3Y+Y2Z+7. The act of permuting can also refer to substitution of symbols, for instance when saying that Y3Z+Z2X+7 is obtained from X3Y+Y2Z+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 k-permutations the order of selection is taken into account, but for k-combinations it is ignored. In fact counting k-permutations is used as a step towards counting the number \tbinom nk of k-combinations, and also towards computing the number n! of permutations of the set (in either of the two meanings mentioned above). However k-permutations 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 ▸

related documents
Uniform space
Taylor series
Subset sum problem
Support vector machine
Multiplication algorithm
Lp space
Fermat number
Truth table
Halting problem
Stochastic process
Ackermann function
BCH code
Basis (linear algebra)
Fundamental theorem of algebra
Lie algebra
Dual space
Euler's formula
Vacuous truth
Primitive recursive function
Bessel function
Polyomino
Continuous function
Probability theory
Convolution
Sorting algorithm
Monte Carlo method
Hyperreal number
Quadratic equation
Relational database
General linear group