Permutation - Wikipedia, the free encyclopedia

/**/








/**/



/**/








Your continued donations keep Wikipedia running!    

Permutation

From Wikipedia, the free encyclopedia

Jump to: navigation, search
For other senses of this word, see permutation (disambiguation).
Permutation is the rearrangement of objects or symbols into distinguishable sequences. Each unique ordering is called a permutation.[1] For example, with the numerals
one to six, each possible ordering consists of a complete list of the
numerals, without repetitions. There are 720 total permutations of
these numerals, one of which is: "4, 5, 6, 1, 2, 3".
The general concept of permutation can be defined more formally in different contexts:

In set theory, 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 sequence "1, 2, 3, 4, 5, 6". A
permutation is distinct from a set or combination, in that the ordering
of elements in a set is not considered relevant. In other words, the
set-theoretic definition of permutation is that of a one-to-one
correspondence, or bijection, of labeled elements with "positions" or "places" which are arranged in a straight line.
In finite geometry, permutative places may be arranged in more geometrically complicated structures than a simple straight line; for instance, a square. For examples, see finite geometry of the square and cube.
In abstract algebra and related areas, the elements of permutation may 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, X, onto itself. This allows for the definition of groups of permutations; see permutation group.
In combinatorics,
the term permutation also has a traditional meaning which includes
ordered lists without repetition and where one or more elements from
the list are omitted from the distinguishable orderings; for example, a
permutation of "1,2,4,3" with "5" and "6" omitted.





Contents
[hide]

1 Counting permutations
2 Abstract algebra
3 Notation
4 Special permutations
5 Permutations in computing
6 Numbering permutations

6.1 Algorithm to generate permutations


7 How to use with a calculator
8 References
9 See also
10 Further reading
11 External links





//

[edit] Counting permutations
In this section only, the traditional definition is used: a
permutation is an ordered list without repetitions, perhaps missing
some elements. The number of permutations of a sequence is:



where:

r is the size of each permutation,
n is the size of the sequence from which elements are permuted, and
! is the factorial operator.

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. To find out how many unique sequences, such as the one previously, we can find, we need to calculate P(10,3) = 720.
An easier way to compute this is to take the first r numbers of n factorial; in this case: take the first 3 numbers in 10 factorial, so you would have 10 times 9 times 8, which equalls 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:



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 of 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 fixing the
element contained in it, so there is no use in writing it explicitly.
Some authors' definition of a cycle do not include cycles of length 1.
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 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.
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 () this following algorithm generates the corresponding permutation of the initial sequence :
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, i.e. the integral quotient without any remainder, and
k mod j is the remainder following integer division of k by j.


[edit] How to use with a calculator
Most calculators have an nPr key. In most advanced desktop
calculators, however, the key is hidden. Example: in TI-83, press MATH,
right three times, and press 2.

[edit] References

^ For cases wherein the ordering of elements is irrelevant, compare combination and set.


[edit] See also






Binomial coefficient
Combination
Combinatorics
Convolution
Cyclic order
Cyclic permutation






Even and odd permutations
Factoradic
Superpattern
Josephus permutation
List of permutation topics
Permutation group
Probability






Random permutation
Rencontres numbers
Sorting network
Substitution cipher
Symmetric group
Twelvefold way
Weak order of permutations







[edit] Further reading

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.
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] External links

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)






Retrieved from "http://en.wikipedia.org/wiki/Permutation"
Categories: Abstract algebra | Combinatorics | Factorial and binomial topics | Permutations






Views


Article
Discussion
Edit this page
History




Personal tools


Sign in / create account






if (window.isMSIE55) fixalpha();

Navigation


Main page
Community portal
Featured content
Current events
Recent changes
Random article
About Wikipedia
Contact us
Make a donation
Help




Search



 





Toolbox


What links here
Related changes
Upload file
Special pages
Printable version Permanent linkCite this article



In other languages


�ęŃ���łаŃ�Ń�ки
Dansk
Deutsch
Espa�ąol
Esperanto
Fran�żais
�śę���
�
Italiano
�ó�ęרית
Lietuvi�ł
Magyar
Nederlands
ćĄćśŹŁ�ś
‪Norsk (bokm�Ąl)�Ź
Polski
Português
� Ń�Ń�Ń�ки�ą
Sloven�ćina
Suomi
Svenska
Ti�żng Vi�t
T�źrk�że
�ŁкŃ�аŃнŃ�ŃŚка
�ż�ą�ŻŁ�









This page was last modified 19:28, 13 March 2007.
All text is available under the terms of the GNU Free Documentation License. (See Copyrights for details.) Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a US-registered 501(c)(3) tax-deductible nonprofit charity.
Privacy policy
About Wikipedia
Disclaimers




if (window.runOnloadHook) runOnloadHook();