Permutation
In mathematics, a permutation of a set can mean one of two different things:
- an arrangement of its members in a sequence or linear order, or
- the act or process of changing the linear order of an ordered set.
Permutations are used in almost every branch of mathematics and in many other fields of science. In computer science, they are used for analyzing sorting algorithms; in quantum physics, for describing states of particles; and in biology, for describing RNA sequences.
The number of permutations of distinct objects is factorial, usually written as, which means the product of all positive integers less than or equal to.
According to the second meaning, a permutation of a set is defined as a bijection from to itself. That is, it is a function from to for which every element occurs exactly once as an image value. Such a function is equivalent to the rearrangement of the elements of in which each element i is replaced by the corresponding. For example, the permutation corresponds to the function defined as
The collection of all permutations of a set form a group called the symmetric group of the set. The group operation is the composition of functions, which results in another function.
In elementary combinatorics, the -permutations, or partial permutations, are the ordered arrangements of distinct elements selected from a set. When is equal to the size of the set, these are the permutations in the previous sense.
Image:Rubik's cube.svg|thumb|In the popular puzzle Rubik's Cube invented in 1974 by Ernő Rubik, each turn of the puzzle faces creates a permutation of the surface colors.
History
Permutation-like objects called hexagrams were used in China in the I Ching as early as 1000 BC.In Greece, Plutarch wrote that Xenocrates of Chalcedon discovered the number of different syllables possible in the Greek language. This would have been the first attempt on record to solve a difficult problem in permutations and combinations.
Al-Khalil, an Arab mathematician and cryptographer, wrote the Book of Cryptographic Messages. It contains the first use of permutations and combinations, to list all possible Arabic words with and without vowels.
The rule to determine the number of permutations of n objects was known in Indian culture around 1150 AD. The Lilavati by the Indian mathematician Bhāskara II contains a passage that translates as follows:
The product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures.
In 1677, Fabian Stedman described factorials when explaining the number of permutations of bells in change ringing. Starting from two bells: "first, two must be admitted to be varied in two ways", which he illustrates by showing 1 2 and 2 1. He then explains that with three bells there are "three times two figures to be produced out of three" which again is illustrated. His explanation involves "cast away 3, and 1.2 will remain; cast away 2, and 1.3 will remain; cast away 1, and 2.3 will remain". He then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three. Effectively, this is a recursive process. He continues with five bells using the "casting away" method and tabulates the resulting 120 combinations. At this point he gives up and remarks:
Now the nature of these methods is such, that the changes on one number comprehends the changes on all lesser numbers,... insomuch that a compleat Peal of changes on one number seemeth to be formed by uniting of the compleat Peals on all lesser numbers into one entire body;
Stedman widens the consideration of permutations; he goes on to consider the number of permutations of the letters of the alphabet and of horses from a stable of 20.
A first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, when Joseph Louis Lagrange, in the study of polynomial equations, observed that properties of the permutations of the roots of an equation are related to the possibilities to solve it. This line of work ultimately resulted, through the work of Évariste Galois, in Galois theory, which gives a complete description of what is possible and impossible with respect to solving polynomial equations by radicals. In modern mathematics, there are many similar situations in which understanding a problem requires studying certain permutations related to it.
The study of permutations as substitutions on n elements led to the notion of group as algebraic structure, through the works of Cauchy.
Permutations played an important role in the cryptanalysis of the Enigma machine, a cipher device used by Nazi Germany during World War II. In particular, one important property of permutations, namely, that two permutations are conjugate exactly when they have the same cycle type, was used by cryptologist Marian Rejewski to break the German Enigma cipher in turn of years 1932–1933.
Definition
In mathematics texts it is customary to denote permutations using lowercase Greek letters.A permutation can be defined as a bijection from a set to itself:
The identity permutation is defined by for all elements, and can be denoted by the number, by, or by a single 1-cycle.
The set of all permutations of a set with n elements forms the symmetric group, where the group operation is composition of functions. Thus for two permutations and in the group, their product is defined by
Composition is usually written without a dot or other sign. In general, composition of two permutations is not commutative; that is, typically the permutations and are not equal.
As a bijection from a set to itself, a permutation is a function that performs a rearrangement of a set, termed an active permutation or substitution. An older viewpoint sees a permutation as an ordered arrangement or list of all the elements of S, called a passive permutation. According to this definition, all permutations in are passive. This meaning is subtly distinct from how passive is used in Active and passive transformation and elsewhere, which would consider all permutations open to passive interpretation.
A permutation can be decomposed into one or more disjoint cycles which are the orbits of the cyclic group acting on the set S. A cycle is found by repeatedly applying the permutation to an element:, where we assume . A cycle consisting of k elements is called a k-cycle.
A fixed point of a permutation is an element x which is taken to itself, that is, forming a 1-cycle. A permutation with no fixed points is called a derangement. A permutation exchanging two elements and leaving the others fixed is called a transposition.
Notations
Several notations are widely used to represent permutations conveniently. The properties of permutations do not depend on the nature of the elements being permuted, only on their number, so one often considers the standard set. Cycle notation is a popular choice, as it is compact and shows the permutation's structure clearly. This article will use cycle notation unless otherwise specified.Two-line notation
's two-line notation lists the elements of S in the first row, and the image of each element below it in the second row. For example, the permutation of S = given by the functioncan be written asThe elements of S may appear in any order in the first row, so this permutation could also be written:
One-line notation
If there is a "natural" order for the elements of S, say, then one uses this for the first row of the two-line notation:Under this assumption, one may omit the first row and write the permutation in one-line notation as
that is, as an ordered arrangement of the elements of S. Care must be taken to distinguish one-line notation from the cycle notation described below: a common usage is to omit parentheses or other enclosing marks for one-line notation, while using parentheses for cycle notation. The one-line notation is also called the word representation.
The example above would then be:
This compact form is common in elementary combinatorics and computer science. It is especially useful in applications where the permutations are to be compared as larger or smaller using lexicographic order.
Cycle notation
Cycle notation describes the effect of repeatedly applying the permutation on the elements of the set S, with an orbit being called a cycle. The permutation is written as a list of cycles; since distinct cycles involve disjoint sets of elements, this is referred to as "decomposition into disjoint cycles".To write down the permutation in cycle notation, one proceeds as follows:
- Write an opening bracket followed by an arbitrary element x of :
- Trace the orbit of x, writing down the values under successive applications of :
- Repeat until the value returns to x, and close the parenthesis without repeating x:
- Continue with an element y of S which was not yet written, and repeat the above process:
- Repeat until all elements of S are written in cycles.
Following the convention of omitting 1-cycles, one may interpret an individual cycle as a permutation which fixes all the elements not in the cycle. Then the list of disjoint cycles can be seen as the composition of these cyclic permutations. For example, the one-line permutation can be written in cycle notation as:
This may be seen as the composition of cyclic permutations
While permutations in general do not commute, disjoint cycles do; for example:
Also, each cycle can be rewritten from a different starting point; for example,
Thus one may write the disjoint cycles of a given permutation in many different ways.
A convenient feature of cycle notation is that inverting the permutation is given by reversing the order of the elements in each cycle. For example,