In
combinatorics, 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
k elements selected from those
n, where
k≤
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 k names on the list. This means that the last member can be filled in (n-k+1) ways.
Summarizing, we find that a total of
- n * (n-1) * (n-2) * ... * (n-k+1)
different permutations of
k objects, taken from a pool of
n objects, exist. If we denote this number
by P(
n,
k) and use the
factorial notation, we can write
- P(n, k) = n! / (n-k)!
See also Combinations, Josephus permutation.
In abstract algebra and other fields, the term permutation is usually reserved for a bijective map from a finite set to itself.
There are two main notations for such permutations.
In relation notation, one can just arrange the "natural" ordering of the elements being permuted on a row, and the new ordering on another row:
- <math>\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{bmatrix}</math>
In FFPA notation, one can write the cycles induced by the permutation; that is, one takes any element (say 1); then the element the first one is being sent to (here 2); then the element this one is sent to (here 5), and so on, until one comes back to the first.
This is a cycle.
The next cycle begins with any other element not considered till now, until every element appears in a cycle.
So the previous permutation has cycle form (1 2 5)(3 4).
Of course, the same permutation could be written as (4 3)(2 5 1), or any other variant, but the "canonical" form for a permutation places the lowest-numbered position in each cycle first in that cycle and then orders the cycles by increasing first element.
FFPA 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 consists 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.
An identity permutation is the permutation which fixes everything.
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.