Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere.... the term permutation is used with different but closely related meanings. They all relate to the notion of mapping the element
Element (mathematics)
In mathematics, an element or member of a Set is any one of the distinct objects that make up that set.... s of a set to other elements of the same set, i.e., exchanging (or "permuting") elements of a set.
general concept of permutation can be defined more formally in different contexts:
a class="link1" onMouseover='showByLink("m53721",this)' onMouseout='hide("m53721")'href="http://www.absoluteastronomy.com/topics/Combinatorics">combinatorics
Combinatorics
Combinatorics is a branch of pure mathematics concerning the study of Countable set objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics.... , a permutation is usually understood to be a sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a Set , it contains Element , and the number of terms is called the length of the sequence.... containing each element from a finite set once, and only once.
Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere.... the term permutation is used with different but closely related meanings. They all relate to the notion of mapping the element
Element (mathematics)
In mathematics, an element or member of a Set is any one of the distinct objects that make up that set.... s of a set to other elements of the same set, i.e., exchanging (or "permuting") elements of a set.
Definitions
The general concept of permutation can be defined more formally in different contexts:
Combinatorics is a branch of pure mathematics concerning the study of Countable set objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics.... , a permutation is usually understood to be a sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a Set , it contains Element , and the number of terms is called the length of the sequence.... containing each element from a finite set once, and only once. The concept of sequence is distinct from that of a set, in that the elements of a sequence appear in some order: the sequence has a first element (unless it is empty), a second element (unless its length is less than 2), and so on. In contrast, the elements in a set have no order; and are different ways to denote the same set.
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
Combination
In combinatorics, a combination is an un-ordered collection of distinct elements, usually of a prescribed size and taken from a given set. Given such a Set S, a combination of elements of S is just a subset of S, where as always for sets the order of the elements is not taken into account .... .
In mathematics and abstract algebra, group theory studies the algebraic structures known as group .The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring , field , and vector spaces can all be seen as groups endowed with additional operations and axioms.... and related areas, the elements of a permutation need not be arranged in a linear order, or indeed in any order at all. Under this refined definition, a permutation is a bijection
Bijection
In mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f = y.... from a finite set
Finite set
In mathematics, finite set is a Set that has a finite number of element . For example,is a finite set with five elements. The number of elements of a finite set is a natural number , and is called the cardinality of the set.... onto itself. This allows for the definition of groups of permutations; see Permutation group
Permutation group
In mathematics, a permutation group is a group G whose elements are permutations of a given Set M, and whose group operation is the composition of permutations in G ; the relationship is often written as .... .
Counting permutations
In this section only, the traditional definition from combinatorics is used: a permutation is an ordered sequence of elements selected from a given finite set, without repetitions, and not necessarily using all elements of the given set. For example, given the set of letters , some permutations are ICE, RING, RICE, NICER, REIGN and CRINGE, but also RNCGI – the sequence need not spell out an existing word. ENGINE, on the other hand, is not a permutation, because it uses the elements E and N twice.
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
Factorial
In mathematics, the factorial of a negative and non-negative numbers integer n, denoted by n!, is the Product of all positive integers less than or equal to n.... 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
n × (n - 1) possible permutations.
For selecting the third element, there are then elements left, giving, for the first three elements together,
n × (n - 1) × (n - 2) possible permutations.
Continuing in this way until there are only 2 elements left, there are 2 choices, giving for the number of possible permutations consisting of elements:
n × (n - 1) × (n - 2) × ... × 2.
The last choice is now forced, as there is exactly one element left. In a formula, this is the number
n × (n - 1) × (n - 2) × ... × 2 × 1
(which is the same as before because the factor 1 does not make a difference). This number is, by definition, the same as n!.
In general the number of permutations is denoted by P(n, r), nPr, or sometimes ,
where:
n is the number of elements available for selection, and
r is the number of elements to be selected (0 = r = n).
For the case where it has just been shown that . The general case is given by the formula:
As before, this can be shown informally by considering the construction of an arbitrary permutation, but this time stopping when the length r has been reached.
The construction proceeds initially as above, but stops at length r. The number of possible permutations that has then been reached is:
P(n, r) = n × (n - 1) × (n - 2) × ... × (n - r + 1).
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
Empty product
In mathematics, an empty product, or nullary product, is the result of multiplication no numbers. Its numerical value is 1 , the multiplicative identity element, just as the empty sum—the result of addition no numbers—is 0 , or the additive identity.... , which always equals 1.
In the example given in the header of this article, with 6 integers , 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:
P(n, r) = n × (n - 1) × (n - 2) × ... × (n - r + 1).
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
Pochhammer symbol
In mathematics, the Pochhammer symbolintroduced by Leo August Pochhammer, represents either the rising or the falling factorial. Unfortunately there is no standard convention about which sort of factorial it represents.... )
n(n + 1)(n + 2)?(n + r − 1)r.
With the rising factorial notation, the number of permutations is (n − r + 1)r.
Permutations in group theory
As explained in a previous section, in group theory the term permutation (of a set) is reserved for a bijective map (bijection
Bijection
In mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f = y.... ) 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 to itself.
More abstractly, a permutation can be considered a filtration (an chain of subsets): the ordering corresponds to the filtration . From the point of view of the field with one element
Field with one element
In mathematics, the field with one element is a suggestive name for an object that "should" exist: many objects in math have properties analogous to objects over a field with elements, where , and the analogy between number fields and function fields is stronger if one includes a field with one element.... , an ordering on a set corresponds to a maximal flag
Flag (linear algebra)
In mathematics, particularly in linear algebra, a flag is an increasing sequence of subspaces of a vector space V. Here "increasing" means each is a proper subspace of the next :... (a filtration on a vector space), considering a set to be a vector space over the field with one element; this connects properties of the symmetric group
Symmetric group
In mathematics, the symmetric group on a Set X, denoted by SX, or Sym, is the group whose underlying set is the set of all bijective function s from X to X, in which the group operation is that of Function composition, i.e., two such functions f and g can be composed to yield a new bijective function ,... and other Coxeter group
Coxeter group
In mathematics, a Coxeter group, named after Harold Scott MacDonald Coxeter, is an group that admits a group presentation in terms of mirror symmetries.... s with properties of algebraic group
Algebraic group
In algebraic geometry, an algebraic group is a group that is an algebraic variety, such that the multiplication and inverse are given by regular functions on the variety.... s.
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 (first example below):
stands for the permutation s of the set 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
Bijection
In mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f = y.... with the set , 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 . (In more mathematical terms, the function
Function (mathematics)
The mathematical concept of a function expresses dependence between two quantities, one of which is known and the other which is produced. A function associates a single output to each input element drawn from a fixed Set , such as the real numbers , although different inputs may have the same output.... that maps a permutation s of E to the permutation f o s o f-1 of is a morphism
Morphism
In mathematics, a morphism is an Abstraction derived from structure-preserving map between two mathematical structures.The study of morphisms and of the structures over which they are defined, is central to category theory.... from the symmetric group
Symmetric group
In mathematics, the symmetric group on a Set X, denoted by SX, or Sym, is the group whose underlying set is the set of all bijective function s from X to X, in which the group operation is that of Function composition, i.e., two such functions f and g can be composed to yield a new bijective function ,... of E into that of , 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 cycle
Cycle (mathematics)
In mathematics, and in particular in group theory, a cycle is a permutation of the elements of some set X which maps the elements of some subset S to each other in a cyclic fashion, while fixing all other elements.... s using cycle notation
Cycle notation
In combinatorics mathematics, the cycle notation is a useful convention for writing down a permutation in terms of its constituent cycle s.... (last three examples above). It works as follows: starting from one element x, we write the sequence (xs(x) s2(x) …) until we get back the starting element (at which point we close the parenthesis without writing the starting element for a second time). This is called the cycle
Cycle (mathematics)
In mathematics, and in particular in group theory, a cycle is a permutation of the elements of some set X which maps the elements of some subset S to each other in a cyclic fashion, while fixing all other elements.... associated to xs 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 (x1x2 … 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
Disjoint
Disjoint may refer to:*Disjoint sets*Disjoint union... support
Support (mathematics)
In mathematics, the support of a function is the set of points where the function is not zero, or the closure of that set. This concept is used very widely in mathematical analysis.... s (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
Up to
In mathematics, the phrase "up to xxxx" indicates that members of an equivalence class are to be regarded as a single entity for some purpose. "xxxx" describes a property or process which transforms an element into one from the same equivalence class, i.e.... cyclic change; see also cycles and fixed points
Cycles and fixed points
In combinatorics mathematics, a cycle of length n of a permutation P over a Set S is a subset of S on which the permutation P acts in the following way:... ). 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.
In informal language, a transposition is a function that swaps two elements of a set. More formally, given a finite set Set , a transposition is a permutation such that there exist indices such that , and for all other indices This is often denoted as ... ; such permutations merely exchange the place of two elements. (Conversely, a matrix transposition
In-place matrix transposition
In-place matrix transposition, also called in-situ matrix transposition, is the problem of transpose an matrix in-place in computer memory: ideally with additional storage, or at most with additional storage much less than .... is itself an important example of a permutation.)
Product and inverse of permutations
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
Function composition
In mathematics, a composite function represents the application of one function to the results of another. For instance, the functions and can be composed by first computing a f and then applying a function g to the output of f.... 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).
In mathematics, if ƒ is a function from A to B then an inverse function for ƒ is a function in the opposite direction, from B to A, with the property that a round trip from A to B to A returns each element of the initial set to itself.... , 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
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an Binary operation that combines any two of its element to form a third element.... .
In abstract algebra, a group isomorphism is a function between two group s that sets up a one-to-one correspondence between the elements of the groups in a way that respects the given group operations.... on permutation groups, obtained by assigning to each permutation its inverse, and this isomorphism is an involution
Involution
In mathematics, an involution, or an involutary function, is a function that is its own inverse function, so that... , 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.
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
Identity function
In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument.... . Conversely, a permutation which changes the position of all elements (no element is mapped to itself) is called a derangement
Derangement
In combinatorics mathematics, a derangement is a permutation in which none of the elements of the set appear in their original positions. That is, it is a bijection f from a Set S into itself with no fixed point : for all x in S, f ≠ x.... .
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
Inverse
Inverse or inversion may refer to:* Inverse , a program for solving inverse and optimization problems* Inversion * Inversion , the reversal of the order of a foot's elements... permutation. It is computed by exchanging each number and the number of the place which it occupies.
In mathematics, when X is a finite set of at least two elements, the permutations of X fall into two classes of equal size: the even permutations and the odd permutations.... 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
Even and odd permutations
In mathematics, when X is a finite set of at least two elements, the permutations of X fall into two classes of equal size: the even permutations and the odd permutations.... 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=(i1i2 … in) and a permutation P, then PQP-1 = (P(i1) P(i2) … P(in)).
In mathematics, a matrix is a rectangular array of numbers, as shown at the right. In addition to a number of elementary, entrywise operations such as matrix addition a key notion is matrix multiplication.... form; the resulting matrix is known as a permutation matrix
Permutation matrix
In mathematics, in matrix theory, a permutation matrix is a square -matrix that has exactly one entry 1 in each row and each column and 0's elsewhere.... .
Properties of permutations
Ascents, descents and runs
An ascent in a permutation is any position i where the following value is bigger than the current one. That is, if is a permutation, then any position i with is called an ascent.
For example, the permutation 3452167 has the ascends 1,2,5,6.
Similarly, a descent is a position i with .
The number of permutations with a given number of ascents or descents is equal to the Eulerian Number
Eulerian number
In combinatorics the Eulerian numberE, oris the number of permutations of the numbers 1 to n in which exactly m elements are greater than the previous element .... , where n is the number of elements of the permutation and k is the given number of ascents or descents.
An ascending run of a permutation is a subsequence of the permutation in which the values raise from position to position.
For example, the permutation 3452167 has the ascending runs 345,2,167.
If a permutation has descents, then it must be the union of k ascending runs. Hence, the number of permutations with k ascending runs is the same as the number of permutations with descents.
Inversions
An inversion, is a pair of entries of a permutation which appear in ascending order, even though the entry that appears first is greater than the entry that appears second.
For example, the permutation 23154 has three inversions: .
The number of permutations with k inversions is expressed by Mahonian numbers
Permutations in computing
Some of the older textbooks look at permutations as assignments, as mentioned above. In computer science
Computer science
Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems.... terms, these are assignment operations, with values
1, 2, …,
n
assigned to variables
x1, x2, …, xn.
Each value should be assigned only once.
The assignment/substitution difference is then illustrative of one way in which functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of function s and avoids program state and immutable object data.... and imperative programming
Imperative programming
In computer science, imperative programming is a programming paradigm that describes computation in terms of statement s that change a program state .... 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
Function composition
In mathematics, a composite function represents the application of one function to the results of another. For instance, the functions and can be composed by first computing a f and then applying a function g to the output of f.... ; functional programmers follow this. In the assignment language a substitution is an instruction to switch round the values assigned, simultaneously; a well-known problem.
In combinatorics, factoradic is a specially constructed number system. Factoradics provide a lexicographical index for permutations, so they have potential application to computer security.... numbers can be used to assign unique numbers to permutations, such that given a factoradic of k one can quickly find the corresponding permutation.
Algorithms to generate permutations
Unordered generation
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)
The formula k mod j returns the least significant digit of k in the factorial base and k := k / j removes that digit, shifting the remaining digits to the right. The first line of the for loop, at each step, swaps 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
Selection sort
Selection sort is a sorting algorithm, specifically an in-place algorithm comparison sort. It has Big O notation complexity, making it inefficient on large lists, and generally performs worse than the similar insertion 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, named after Ronald Fisher and Frank Yates, also known as the Knuth shuffle, after Donald Knuth, is an algorithm for generating a random permutation of a finite set?in plain terms, for randomly shuffling the set.... is based on the same principle as this algorithm.
Lexicographical order generation
For every number k, with 0 = k < n!, the following algorithm generates the corresponding lexicographical permutation of the initial sequence sj, j= 1…n:
In mathematics, a quotient is the result of a division . For example, when dividing 6 by 3, the quotient is 2, while 6 is called the division , and 3 the divisor.... without any remainder
Remainder
In arithmetic, when the result of the division of two integers cannot be expressed with an integer quotient, the remainder is the amount "left over."... , and
In arithmetic, when the result of the division of two integers cannot be expressed with an integer quotient, the remainder is the amount "left over."... following integer division of
k by j.
s[n] denotes the
nth element of sequence s.
A Java implementation:
static public E[] permutation(E[] s, int num)
An Actionscript implementation:
function permutation(n:Number, k:Number):Array
A calculator is a device for performing mathematical calculations, distinguished from a computer by having a limited problem solving ability and an interface optimized for interactive calculation rather than programming.... s 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.
A spreadsheet is a computer application that simulates a paper worksheet. It displays multiple cells that together make up a grid consisting of rows and columns, each cell containing either alphanumeric text or numeric values.... also provides a built-in function for calculating the number of permutations, called PERMUT in many popular spreadsheets. Apple's Numbers '08
Numbers (software)
Numbers is a spreadsheet application developed by Apple Inc. as part of the iWork productivity suite alongside Keynote and Pages. Numbers 1.0 was announced on August 7 2007 and runs on Mac OS X v10.4 and Mac OS X v10.5 only.... software notably did not include such a function but this was rectified in Apple's Numbers '09
Numbers (software)
Numbers is a spreadsheet application developed by Apple Inc. as part of the iWork productivity suite alongside Keynote and Pages. Numbers 1.0 was announced on August 7 2007 and runs on Mac OS X v10.4 and Mac OS X v10.5 only.... software package.
