From Wikipedia, the free encyclopedia

Permutation is the rearrangement of objects or symbols into distinguishable sequences. Each unique ordering is called a permutation. ^[1] For example, with the numerals one to six, each possible ordering consists of a complete list of the numerals, without repetitions. There are 720 total permutations of these numerals, one of which is: "4, 5, 6, 1, 2, 3".

The general concept of permutation can be defined more formally in different contexts:

• In set theory, a permutation is an ordered sequence containing each symbol from a set once, and only once. A permutation is distinct from a set or combination, in that the ordering of elements in a set is not considered relevant for sets or combinations. In other words, the set-theoretic definition of permutation is that of a one-to-one correspondence, or bijection, of labeled elements with "positions" or "places" which are arranged in a straight line.
• In abstract algebra and related areas, the elements of permutation may not be arranged in a linear order, or indeed in any order at all. Under this refined definition, a permutation is a bijection from a finite set, X, onto itself. This allows for the definition of groups of permutations; see permutation group.
• In combinatorics, the term permutation also has a traditional meaning which includes ordered lists without repetition and where one or more elements from the list are omitted from the distinguishable orderings; for example, a permutation of "1,2,4,3" with "5" and "6" omitted.

Contents 1 Counting permutations 2 Abstract algebra 3 Notation 4 Product and inverse of permutations 5 Special permutations 6 Permutations in computing 7 Numbering permutations 7.1 Algorithms to generate permutations 7.1.1 Unordered generation 7.1.2 Lexicographical order generation 8 Software and hardware implementations 8.1 Calculator functions 8.2 Spreadsheet functions 9 See also 10 Notes 11 References 12 External links

In this section only, the traditional definition is used: a permutation is an ordered list without repetitions, perhaps missing some (n−r) elements. The number of permutations of a sequence is denoted by P(n, r) or sometimes and is given by the formula:

where:

• r is the size of each permutation,
• n is the size of the set from which elements are permuted, and
• ! is the factorial operator.

For example, if we have a total of 10 elements, the integers {1, 2 .. 10}, one sequence of three elements from this set would be (5, 3, 4). In this case, n = 10 and r = 3. To find out how many unique sequences we can find, we need to calculate P(10,3) = 10! / (10−3)! = (1×2×3×4×5×6×7×8×9×10) / (1×2×3×4×5×6×7) = 8×9×10 = 720

In the case only where n = r then the formula above as in pure mathematics simplifies to:

The reason why 0! (zero factorial) is 1, is because in set theory an empty set can only be ordered one way, so 0! = 1. If n = 0 then there is also one unique sequence.

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.

If n > 1 and r > 1, each permutations element order becomes significant. For example the permutations of 3 elements in the set {1, 2, 3} taken in sequence lengths of 2 is:

 (1,2), (1,3), (2,1), (2,3), (3,1) and (3,2).   6 permutations for sequence lengths of 2 

This should not be confused with combination where the order of the elements is not taken into account and the above elements in the same set combine into just the 3 combinations for the same lengths:

 (1,2), (1,3) and (2,3).    3 combinations for collection lengths of 2

Other, older notations include ⁿP_r, P_n,r, or _nP_r. 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)

n(n + 1)(n + 2)⋯(n + r − 1)r.

With the rising factorial notation, the number of permutations is (n − r + 1)_r.

As explained in a previous section, in abstract algebra and other mathematical fields, the term permutation (of a set) is now reserved for a bijective map (bijection) from a finite set onto itself. The earlier example, of making permutations out of numbers 1 to 10, would be translated as a map from the set {1, …, 10} 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:

stands for the permutation s of the set {1,2,3,4,5} defined by s(1)=2, s(2)=5, s(3)=4, s(4)=3, s(5)=1.

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⁻¹ 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) s²(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 (x₁ x₂ … x_L) stands for the permutation that maps x_i on x_i+1 (i=1…L−1) and x_L on x₁, 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).

Obviously, a 1-cycle (cycle of length 1) is the same as fixing the element contained in it, so there is no use in writing it explicitly. Some authors' definition of a cycle do not include 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.)

Main article: Symmetric group

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 an inverse, so do permutations, and both P ∘ P⁻¹ and P⁻¹ ∘ 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)⁻¹ = Q⁻¹ ∘ P⁻¹, from an abstract point of view it is immaterial whether PQ represents "P before Q" or "P after Q". For concrete permutations, the distinctions is, of course, in general quite material.

If we think of a permutation that "changes" the position of the first element to the first element, the second to the second, and so on, we really have not changed the positions of the elements at all. Because of its action, we describe it as the identity permutation because it acts as an identity function. Conversely, a permutation which changes the position of all elements (no element is mapped to itself) is called a derangement.

If one has some permutation, called P, one may describe a permutation, written P⁻¹, which undoes the action of applying P. In essence, performing P then P⁻¹ 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=(i₁ i₂ … i_n) and a permutation P, then PQP⁻¹ = (P(i₁) P(i₂) … P(i_n)).

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

1, 2, …, n

assigned to variables

x₁, x₂, …, x_n.

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 s_j, j=1…n:

 function permutation(k, s) {
     var int factorial:= 1;
     for j= 2 to length(s) {
        factorial:= factorial* (j-1);        // factorial= (j-1)!
        swap s[j- ((k / factorial) mod j)] with s[j];
     }
     return s;
 }

For every number k, with 0 ≤ k < n!, the following algorithm generates the corresponding lexicographical permutation of the initial sequence s_j, 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

• k / j denotes integer division of k by j, i.e. the integral quotient without any remainder, and
• k mod j is the remainder following integer division of k by j.
• s[n] denotes the nth element of sequence s.

Most calculators have a built-in function for calculating the number of permutations, called nPr or PERM on many. The permutations function is often only available through several layers of menus; how to access the function is usually indicated in the documentation for calculators that support it.

Most spreadsheet software also provides a built-in function for calculating the number of permutations, called PERMUT in many popular spreadsheets. Apple's Numbers software notably does not currently include such a function^[2].

• Miklos Bona. "Combinatorics of Permutations", Chapman Hall-CRC, 2004. ISBN 1-58488-434-7.
• Donald Knuth. The Art of Computer Programming, Volume 4: Generating All Tuples and Permutations, Fascicle 2, first printing. Addison-Wesley, 2005. ISBN 0-201-85393-0.
• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.1: Combinatorial Properties of Permutations, pp.11–72.

• A review of permutations from plainmath.net
• Many Common types of permutation and combination math problems, with detailed solutions
• Permutations and Puzzles on Graphs
• Free Permutation/Combination/Factorial Calculator (with source code)