Permutation
In mathematics, a permutation describes two differing, but related ideas.
In a basic sense, a permutation is a sequence of elements chosen from a chosen set, rearranged in a specific order, such that no element chosen appears more than once. In this rearrangement, unlike in a set, the order in which the elements are written down matters.
Counting permutations
There are clearly many different ways to rearrange objects. Specifically, how many permutations can we create, on chosing r elements, from a total pool of n distinct objects at your disposal (with r≤n).
For example, if we have a total of 10 elements, the integers {0, 1, ..., 10}, a permutation of three elements from this set is {2,3,1}. In this case, n = 10 and r = 3.
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.
Summarizing, we find that a total of
- n(n-1)(n-2) ...(n-r+1)
different permutations of r objects, taken from a pool of n objects, exist. If we denote this number by P(n, r) and use the factorial notation, we can write
- .
In the above example, we have n = 10 and r = 3, so to find out how many unique sets, such as the one previously, we can find, we need to calculate P(10,3) = 720.
Other, older notations include nPr, Pn,r, or nPr. Often, when using TeX or otherwise, the P(n,r) method is the simplest to typeset.
In modern mathematical terminology, such as that used in professional combinatorics, the word permutation is now rarely used except in the case r=n.
Abstract algebra
In abstract algebra and other fields, the term permutation is usually reserved for a bijective map from a set to itself. What we have just explored is, in essence, the same thing. Our previous example of making permutations out of numbers 1 to 10 would be a map from the set {0, ..., 10} 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 notation, one can just arrange the "natural" ordering of the elements being permuted on a row, and the new ordering on another row:
This means that in the first position, the second element of the set should be placed, in the second position, the fifth element in the set should be placed, and so on. Alternatively, if we have a finite set of elements (which need not be integers), we can firstly create an association between each element and an integer - more precisely, we can create a mapping ν(s) : S -> Z where ν is bijective, and S is our pool of elements. One can then read the above notation as mapping the element ν-1(1) to element ν-1(2), element ν-1(2) to element ν-1(5), and so on.
Alternatively, we can write the permutation in terms of how the elements change when the permutation is applied. If we look at the above permutation as an example, if we take an element in the first position, on applying the permutation it is then placed in the second position. On applying the permutation again it is placed in the firth position, and if we were to apply the permutation again we see that the element has now returned to the first permutation. We say that the behaviour of such an element is a cycle, and we can write this cycle as (1 2 5). The next cycle begins with any other element not considered till now, until every element appears in a cycle.
As such, we can write the permutation as a set of cycles. The previous permutation just considered 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.
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), since a cycle of just one element has no effect.
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. A special terminology is used to describe cycles of length two - these are transpositions - since in a length two cycle, the elements are merely transposed.
Special permutations
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 it's action, we describe it as the identity permutation because it acts as an identity function.
If we have some permutation called P, the identity permutation I, we can describe a permutation, written P-1, which undoes the action of applying P. In essence, performing P then P-1 is the same as performing the identity permutation. We always have such a permutation since a permutation is a bijective map. Such a permutation is called the inverse permutation.
One can define the product of two permutations. If we have to permutations, P and Q, the action of performing P and Q will be the same as performing some other permutation, R, itself. Note that R could be P or Q. The product of P and Q is defined to be the permutation R. For more, see Symmetric group and Permutation group.
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.
We can also represent a permutation in matrix form - the following matrix is known as a permutation matrix.
See also
In music and the terminology of the twelve tone technique a permutation is one of the many forms a tone row or twelve tone series. That is, prime form and any transposition, inversion, retrograde or retrograde-inversion, a total of 48 permutations. However, not all prime series will yield so many variations because tranposed and/or inverse transformations may be identical to each other. This is known as invariance.