Permutation

From Wikipedia, the free encyclopedia

For other uses, see Permutation (disambiguation).

The concept of a permutation expresses the idea that distinguishable objects may be arranged in various different orders. For instance, with the numbers one to six, each possible order makes a list of the numbers, without repetitions. One such permutation is: "3, 4, 6, 1, 2, 5".

There are a number of ways in which the permutation concept may be defined more formally. A permutation is an ordered sequence containing each symbol from a set once and only once; neither "1, 2, 2, 3, 4, 5, 6" nor "1, 2, 4, 5, 6" are permutations of the set "1, 2, 3, 4, 5, 6." One can therefore point to the essential difference between a permutation and a set: the elements of a permutation are arranged in a specified order. In other words, the non-technical definition of permutation is that of a one-to-one correspondence, or bijection, of labeled elements with "positions" or "places" that are arranged in a straight line. In more technical contexts, the elements may not be arranged in a linear order, or indeed in any order at all. This suggests the following redefinition:

In mathematics, especially in abstract algebra and related areas, a permutation is a bijection from a finite set X onto itself. This lets us define "groups" of permutations; see permutation group.

Once we have defined groups of permutations that act on sets of labeled elements, we may wish to again associate the elements with geometric "positions" or "places," as in the non-technical definition above. The places may be arranged in a straight line, as in the non-technical definition, or in a more complicated structure-- for instance, a square. For examples, see finite geometry of the square and cube.

In combinatorics, the term permutation also has a traditional meaning not much in use anymore, which is used to include ordered lists without repetition, but not exhaustive (so of less than maximum length).

Contents

[edit] Counting permutations

In this section only, the traditional definition is used: a permutation is an ordered list without repetitions, perhaps missing some elements. It is easy to count the number of permutations of size r when chosen from a set of size n (with r ≤ n).

For example, if we have a total of 10 elements, the integers {1, 2, ..., 10}, a permutation of three elements from this set is (5, 3, 4). In this case, n = 10 and r = 3. So how many ways can this completely be done?

  1. We can pretend to select the first member of all permutations out of n choices because there are n distinct elements from the generating set.
  2. Next, since we have used one of the n elements already, the second member of the permutation has (n − 1) elements to choose from the remaining set.
  3. The third member can be filled in (n − 2) ways since 2 have been used already.
  4. This pattern continues until there are r members on the permutation. This means that the last member can be filled in (n − (r − 1) ) = (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

P_r^n = \frac{n!}{(n-r)!}

In the above example, we have n = 10 and r = 3, so to find out how many unique sequences, 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.

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).

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

[edit] Abstract algebra

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.

[edit] Notation

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:

\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{bmatrix}

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-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) 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 (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 the cycle. Since these cycles have by construction disjoint support)s (i.e. they act non-trivially on disjoint subsets of E), they do commute (i.e. (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, of course (up to cyclic change, see also cycles and fixed points).

Obviously, a 1-cycle (cycle of length 1) is the same as the identity map idE, so there is no use in writing it, since (x1) is just the same than (x) for any other x, namely idE. According to most author's definition of a cycle (i.e.: a permutation having exactly one nontrivial orbit), a 1-cycle isn't a cycle, in fact.

Cycles of length two are called transpositions; such permutations merely exchange ("the place of") two elements.

[edit] 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 its action, we describe it as the identity permutation because it acts as an identity function.

If we have some permutation called P, 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 two 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.

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.

[edit] Permutations in computing

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

x1, x2, ..., xn.

Each value should be assigned just 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.

[edit] Numbering permutations

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.

[edit] Algorithm to generate permutations

For every number k (0 \le k < n!) this following algorithm generates the corresponding permutation of the initial sequence \left( s_j \right)_{j=1}^n:

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

Notation

  • k / j denotes integer division of k by j without rest, and
  • k mod j is the remaining rest of the integer division of k by j.

[edit] See also

[edit] References

  • 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.

[edit] See also

  • 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.

[edit] External links

Retrieved from "http://en.wikipedia.org../../../p/e/r/Permutation.html"