In mathematics, a permutation is a sequence of elements in which no element appears more than once. In a sequence, unlike in a set, the order in which the elements are written down matters. Suppose you have a total of n distinct objects at your disposal and you want to create permutations of r elements selected from those n, where r≤n.
In how many ways can that be done?
- We can select the first member of the list in n ways because there are n distinct elements.
- The second member of the list can be filled in (n-1) ways since we have used up one of the n elements already.
- The third member can be filled in (n-2) ways since 2 have been used already.
- This pattern continues until there are r names on the list. This means that the last member can be filled in (n-r+1) ways.
- n * (n-1) * (n-2) * ... * (n-r+1)
In modern mathematical terminology, such as that used in professional combinatorics, the word permutation is now rarely used except in the case r=n.
In abstract algebra and other fields, the term permutation is usually reserved for a bijective map from a set to itself. Some of the older textbooks do look at permutations an alternative way (essentially as assignment operations); the difference could be used to illustrate one way in which functional programming and imperative programming differ. The convention, though, is now that permutations are just functions and the operation on them is function composition.
There are two main notations for such permutations. In relation notational, one can just arrange the "natural" ordering of the elements being permuted on a row, and the new ordering on another row:
This notation often omits fixed points, that is, elements mapped to themselves; thus (1 3)(2)(4 5) can become simply (1 3)(4 5).
A permutation consisting of one cycle is itself called a cycle. The number of entries of a cycle is called the length. For example, the length of (1 2 5) is three.
The identity permutation is the permutation which maps each element to itself.
Given a permutation P, the identity permutation I, P's inverse permutation P-1 is the permutation that undoes P, ie., performing P then P-1 is the same as performing the identity permutation.
A transposition is a permutation which exchanges two elements and keeps all others fixed. For example (1 3) is a transposition. A transposition is a cycle of length two.
One can define product of two permutations, see Symmetric group and Permutation group. An even permutation is a permutation which can be expressed as a product of even number of transpositions, and the identity permutation is a even permutation as it equals (1 2)(1 2). An odd permutation is an permutation which can be expressed as a product of odd number of transpositions.
A permutation matrix is a matrix representation of permutation.