Dictionary Definition
permutation
Noun
1 an event in which one thing is substituted for
another; "the replacement of lost blood by a transfusion of donor
blood" [syn: substitution, transposition, replacement, switch]
2 the act of changing the arrangement of a given
number of elements
3 complete change in character or condition; "the
permutations...taking place in the physical world" Henry
Miller
4 act of changing the lineal order of objects in
a group
User Contributed Dictionary
Pronunciation

 Rhymes: eɪʃǝn
Noun
 A onetoone mapping from a finite set to itself.
 This permutation takes each element to the one following it, with the last mapped back to the first.
 An ordering of a finite set of distinct elements.
 There are six permutations of three elements, e.g. .
 Any reordering of an ordered set of pitch classes (DeLone et. al. (Eds.), 1975, chap. 6), often the transposition, inversion, retrograde, or retrogradeinversion
Translations
onetoone mapping
 Czech: permutace
 Finnish: permutaatio
 Portuguese: permutação
 Swedish: permutation
ordering of a set of distinct elements
 Czech: permutace
 Finnish: permutaatio
 Portuguese: permutação
 Swedish: permutation
reordering of an ordered set of pitch classes
 Finnish: muunnos, transponointi
 Portuguese: permutação
 ttbc Bulgarian: пермутация f
 ttbc Estonian: permutatsioon
 ttbc German: Permutation f
 ttbc Latin: permutatio
 ttbc Slovak: permutácia f
See also
References
 DeLone et. al. (Eds.) (1975). Aspects of TwentiethCentury Music. Englewood Cliffs, New Jersey: PrenticeHall. ISBN 0130493465, Ch. 6.
French
Etymology
From permutationem (nominative: permutatio), from permutatus (past participle of permutare).Swedish
Noun
permutation permutation; onetoone mapping of a finite set to itself
 permutation; an ordering of a finite set of distinct elements
See also
Extensive Definition
In several fields of mathematics the term
permutation is used with different but closely related meanings.
They all relate to the notion of mapping the elements
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:In combinatorics
In combinatorics, a permutation is usually understood to be a 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.
In group theory
In group theory 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 from a finite set onto itself. This allows for the definition of groups of permutations; see Permutation group.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 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 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.
 n × (n − 1) × (n − 2) possible permutations.
 n × (n − 1) × (n − 2) × ... × 2.
 n × (n − 1) × (n − 2) × ... × 2 × 1
In general the number of permutations is denoted
by P(n, r), nPr, or sometimes P_r^n, 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:
 P(n, r) = \frac.
 P(n, r) = n × (n − 1) × (n − 2) × ... × (n − r + 1).
 n! = n × (n − 1) × (n − 2) × ... × 2 × 1
 = n × (n − 1) × (n − 2) × ... × (n − r + 1) × (n − r) × ... × 2 × 1
 = P(n, r) × (n − r) × ... × 2 × 1
 = P(n, r) × (n − r)!.
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),
 P(10,3) = \frac = \frac = \frac = 8 \times 9 \times 10 = 720
In the special case where n = r the
formula above simplifies to:
 P(n,r) = \frac = \frac = n!
The reason why 0! = 1 is that 0! is an empty
product, 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 n! 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)
 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) 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.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
If we have a finite set E of n elements, it is by
definition in bijection 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
that maps a permutation s of E to the permutation f o s o f−1 of is
a morphism from the
symmetric
group 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 cycles.
It works as follows: starting from one element x, we write the
sequence (x s(x) s2(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 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 (x1 x2 … xL) stands for the
permutation that maps xi on xi+1 (i=1…L−1) and x'L on x1, 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 nontrivially 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 1cycle (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 does 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.)
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
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 inverses,
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.
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)−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. 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−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 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=(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.
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 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 wellknown
problem.
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.
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 first line in the for loop is constructing
the Factorial
base representation of k  the important thing here is that
for each k, it generates a unique corresponding sequence of n
integers where the first number is in , the second is in , etc.
Thus what the second line is doing is , at each step, swapping 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, first putting the nth element in the correct place, then
the n1st, etc. Since there is exactly one way to selection sort a
permutation, this algorithm generates a unique permutation for each
choice of k.
The FisherYates
shuffle 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:
function permutation(k, s)
Notation
Software and hardware implementations
Calculator functions
Most calculators have a builtin 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.Spreadsheet functions
Most spreadsheet software also provides a builtin 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.See also
 Alternating permutation
 Binomial coefficient
 Combination
 Combinatorics
 Convolution
 Cyclic order
 Cyclic permutation
 Even and odd permutations
 Factoradic
 Superpattern
 Josephus permutation
 List of permutation topics
 LeviCivita symbol
 Permutation group
 Probability
 Random permutation
 Rencontres numbers
 Sorting network
 Substitution cipher
 Symmetric group
 Twelvefold way
 Weak order of permutations
Notes
References
 Miklos Bona. "Combinatorics of Permutations", Chapman HallCRC, 2004. ISBN 1584884347.
 Donald Knuth. The Art of Computer Programming, Volume 4: Generating All Tuples and Permutations, Fascicle 2, first printing. AddisonWesley, 2005. ISBN 0201853930.
 Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. AddisonWesley, 1998. ISBN 0201896850. Section 5.1: Combinatorial Properties of Permutations, pp.11–72.
External links
 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)
 Software for Permutation and Combination
 Webbased calculator of permutations and combinations
permutation in Bulgarian: Пермутация
permutation in Czech: Permutace
permutation in Danish: Permutation
permutation in German: Permutation
permutation in Spanish: Permutación
permutation in Esperanto: Permutaĵo
permutation in French: Permutation
permutation in Korean: 순열
permutation in Indonesian: Permutasi
permutation in Italian: Permutazione
permutation in Hebrew: תמורה (מתמטיקה)
permutation in Lithuanian: Kėliniai
permutation in Hungarian: Permutáció
permutation in Dutch: Permutatie
permutation in Japanese: 順列
permutation in Norwegian: Permutasjon
permutation in Polish: Permutacja
permutation in Portuguese: Permutação
permutation in Russian: Перестановка
permutation in Slovak: Permutácia
(algebra)
permutation in Finnish: Permutaatio
permutation in Swedish: Permutation
permutation in Tamil: வரிசைமாற்றம்
permutation in Thai: การเรียงสับเปลี่ยน
permutation in Vietnamese: Hoán vị
permutation in Turkish: Permütasyon
permutation in Ukrainian: Перестановка
permutation in Urdu: تبدل کامل
permutation in Chinese: 置換
Synonyms, Antonyms and Related Words
alteration, alternation, avatar, battledore and
shuttlecock, catabolism, catalysis, commutation, consubstantiation,
cooperation,
counterchange,
cross fire, displacement, exchange, giveandtake,
heterotopia,
innovation, interchange, intermutation, interplay, lex talionis,
measure for measure, metabolism, metagenesis, metamorphism, metamorphosis, metastasis, metathesis, metempsychosis, modification, mutant, mutated form, mutation, mutual admiration,
mutual support, mutual transfer, mutuality, novelty, quid pro quo, reciprocality, reciprocation, reciprocity, reincarnation, retaliation, something for
something, sport, tit for
tat, transanimation, transfiguration,
transfigurement,
transformation,
transformism,
translation,
translocation,
transmigration,
transmogrification,
transmutation,
transposal, transposition, transubstantiation,
vicissitude