However, there is also a traditional more general meaning of the term "permutation" used in combinatorics. In this more general sense, permutations are those sequences in which, as before, each element occurs at most once, but not all elements of the given set need to be used.
For a related notion in which the ordering of the selected elements form a set, for which the ordering is irrelevant, see Combination.
If n denotes the size of the set – the number of elements available for selection – and only permutations are considered that use all n elements, then the total number of possible permutations is equal to n!, where "!" is the factorial operator. This can be shown informally as follows. In constructing a permutation, there are n possible choices for the first element of the sequence. Once it has been chosen, elements are left, so for the second element there are only possible choices. For the first two elements together, that gives us
In general the number of permutations is denoted by P(n, r), nPr, or sometimes , where:
For the case where it has just been shown that . The general case is given by the formula:
For example, if there is a total of 10 elements and we are selecting a sequence of three elements from this set, then the first selection is one from 10 elements, the next one from the remaining 9, and finally from the remaining 8, giving . In this case, n = 10 and r = 3. Using the formula to calculate P(10,3),
In the special case where n = r the formula above simplifies to:
The reason why 0! = 1 is that 0! is an empty product, which always equals 1.
In the example given in the header of this article, with 6 integers {1..6}, this would be: P(6,6) = 6! / (6−6)! = (1×2×3×4×5×6) / 0! = 720 / 1 = 720.
Since it may be impractical to calculate if the value of n is very large, a more efficient algorithm is to calculate:
Other, older notations include nPr, Pn,r, or nPr. A common modern notation is (n)r which is called a falling factorial. However, the same notation is used for the rising factorial (also called Pochhammer symbol)
With the rising factorial notation, the number of permutations is (n − r + 1)r.
If we have a finite set E of n elements, it is by definition in bijection with the set {1,…,n}, where this bijection f corresponds just to numbering the elements. Once they are numbered, we can identify the permutations of the set E with permutations of the set {1,…,n}. (In more mathematical terms, the function that maps a permutation s of E to the permutation f o s o f−1 of {1,…,n} is a morphism from the symmetric group of E into that of {1,…,n}, see below.)
Alternatively, we can write the permutation in terms of how the elements change when the permutation is successively applied. This is referred to as the permutation's decomposition in a product of disjoint cycles. It works as follows: starting from one element x, we write the sequence (x s(x) s2(x) …) until we get back the starting element (at which point we close the parenthesis without writing it for a second time). This is called the cycle associated to x's orbit following s. Then we take an element we did not write yet and do the same thing, until we have considered all elements. In the above example, we get: s = (1 2 5) (3 4).
Each cycle (x1 x2 … xL) stands for the permutation that maps xi on xi+1 (i=1…L−1) and xL on x1, and leaves all other elements invariant. L is called the length of the cycle. Since these cycles have by construction disjoint supports (i.e. they act non-trivially on disjoint subsets of E), they do commute (for example, (1 2 5) (3 4) = (3 4)(1 2 5)). The order of the cycles in the (composition) product does not matter, while the order of the elements in each cycles does matter (up to cyclic change; see also cycles and fixed points). The canonical way of representing such cycles is to start by the smallest element of each cycle.
A 1-cycle (cycle of length 1) simply fixes the element contained in it, so it is often not written explicitly. Some authors define a cycle to exclude cycles of length 1.
Cycles of length two are called transpositions; such permutations merely exchange the place of two elements. (Conversely, a matrix transposition is itself an important example of a permutation.)
One can define the product of two permutations as follows. If we have two permutations, P and Q, the action of first performing P and then Q will be the same as performing some single permutation R. The product of P and Q is then defined to be that permutation R. Viewing permutations as bijections, the product of two permutations is thus the same as their composition as functions. There is no universally agreed notation for the product operation between permutations, and depending on the author a formula like PQ may mean either P ∘ Q or Q ∘ P. Since function composition is associative, so is the product operation on permutations: (P ∘ Q) ∘ R = P ∘ (Q ∘ R).
Likewise, since bijections have inverses, so do permutations, and both P ∘ P−1 and P−1 ∘ P are the "identity permutation" (see below) that leaves all positions unchanged. Thus, it can be seen that permutations form a group.
As for any group, there is a group isomorphism on permutation groups, obtained by assigning to each permutation its inverse, and this isomorphism is an involution, giving a dual view on any abstract result. Since (P ∘ Q)−1 = Q−1 ∘ P−1, from an abstract point of view it is immaterial whether PQ represents "P before Q" or "P after Q". For concrete permutations, the distinction is, of course, quite material.
If one has some permutation, called P, one may describe a permutation, written P−1, which undoes the action of applying P. In essence, performing P then P−1 is equivalent to performing the identity permutation. One always has such a permutation since a permutation is a bijective map. Such a permutation is called the inverse permutation. It is computed by exchanging each number and the number of the place which it occupies.
An even permutation is a permutation which can be expressed as the product of an even number of transpositions, and the identity permutation is an even permutation as it equals (1 2)(1 2). An odd permutation is a permutation which can be expressed as the product of an odd number of transpositions. It can be shown that every permutation is either odd or even and can't be both.
One theorem regarding the inverse permutation is the effect of a conjugation of a permutation by a permutation in a permutation group. If we have a permutation Q=(i1 i2 … in) and a permutation P, then PQP−1 = (P(i1) P(i2) … P(in)).
We can also represent a permutation in matrix form; the resulting matrix is known as a permutation matrix.
Some of the older textbooks look at permutations as assignments, as mentioned above. In computer science terms, these are assignment operations, with values
assigned to variables
Each value should be assigned only once.
The assignment/substitution difference is then illustrative of one way in which functional programming and imperative programming differ — pure functional programming has no assignment mechanism. The mathematics convention is nowadays that permutations are just functions and the operation on them is function composition; functional programmers follow this. In the assignment language a substitution is an instruction to switch round the values assigned, simultaneously; a well-known problem.
Factoradic numbers can be used to assign unique numbers to permutations, such that given a factoradic of k one can quickly find the corresponding permutation.
For every number k, with 0 ≤ k < n!, the following algorithm generates a unique permutation of the initial sequence sj, j=1…n:
function permutation(k, s) {
for j= 2 to length(s) {
k:= k/ (j-1); // integer division cuts off the remainder
swap s[(k mod j)+ 1] with s[j]; //note that our array is indexed starting at 1}
return s;
}The first line in the for loop is constructing the Factorial base representation of k -- the important thing here is that for each k, it generates a unique corresponding sequence of n integers where the first number is in {0,1}, the second is in {0,1,2}, etc. Thus what the second line is doing is , at each step, swapping the jth element with one of the elements that are currently before it. If we consider the swaps in reverse order, we see that it implements a backwards Selection sort, first putting the nth element in the correct place, then the n-1st, etc. Since there is exactly one way to selection sort a permutation, this algorithm generates a unique permutation for each choice of k.
The Fisher-Yates shuffle is based on the same principle as this algorithm.
For every number k, with 0 ≤ k < n!, the following algorithm generates the corresponding lexicographical permutation of the initial sequence sj, j= 1…n:
function permutation(k, s) {
var int n:= length(s); factorial:= 1;
for j= 2 to n- 1 { // compute (n- 1)!
factorial:= factorial* j;}
for j= 1 to n- 1 {
tempj:= (k/ factorial) mod (n+ 1- j);
temps:= s[j+ tempj]
for i= j+ tempj to j+ 1 step -1 {
s[i]:= s[i- 1]; // shift the chain right}
s[j]:= temps;
factorial:= factorial/ (n- j);}
return s;
}Notation
|
|
|
|
|
|
|
|
|
|
|