Permutation

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a permutation of a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> can mean one of two different things:

<ul><li>an arrangement of its members in a <a href="/facts/Sequence/gV2S4uqp">sequence</a> or <a href="/facts/Linear_order/xnTtmuYJ">linear order</a>, or</li>
<li>the act or process of changing the linear order of an ordered set.</li></ul>
An example of the first meaning is the six permutations (orderings) of the set {1, 2, 3}: written as <a href="/facts/Tuple/BI1HIxL8">tuples</a>, they are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). <a href="/facts/Anagram/T8L7yImr">Anagrams</a> of a word whose letters are all different are also permutations: the letters are already ordered in the original word, and the anagram reorders them. The study of permutations of <a href="/facts/Finite_set/za1newlP">finite sets</a> is an important topic in <a href="/facts/Combinatorics/k14xUoKT">combinatorics</a> and <a href="/facts/Group_theory/NfowcI5H">group theory</a>.
Permutations are used in almost every branch of mathematics and in many other fields of science. In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, they are used for analyzing <a href="/facts/Sorting_algorithm/PwHpj1Gs">sorting algorithms</a>; in <a href="/facts/Quantum_physics/BRc3Mzgr">quantum physics</a>, for describing states of particles; and in <a href="/facts/Biology/1M1ee3pB">biology</a>, for describing <a href="/facts/RNA/HxPeNfNj">RNA</a> sequences.
The number of permutations of n distinct objects is n <a href="/facts/Factorial/kkfy1Bwe">factorial</a>, usually written as n!, which means the product of all positive integers less than or equal to n.
According to the second meaning, a permutation of a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> S is defined as a <a href="/facts/Bijection/j4gTuTmW">bijection</a> from S to itself. That is, it is a <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> from S to S for which every element occurs exactly once as an <a href="/facts/Image_(mathematics)/KANefMAl">image</a> value. Such a function 
 
 
 
 σ
 :
 S
 →
 S
 
 
 {\displaystyle \sigma :S\to S}
 
 is equivalent to the rearrangement of the elements of S in which each element i is replaced by the corresponding 
 
 
 
 σ
 (
 i
 )
 
 
 {\displaystyle \sigma (i)}
 
. For example, the permutation (3, 1, 2) corresponds to the function 
 
 
 
 σ
 
 
 {\displaystyle \sigma }
 
 defined as

σ
        (
        1
        )
        =
        3
        ,
        
        σ
        (
        2
        )
        =
        1
        ,
        
        σ
        (
        3
        )
        =
        2.
      
    
    {\displaystyle \sigma (1)=3,\quad \sigma (2)=1,\quad \sigma (3)=2.}

The collection of all permutations of a set form a <a href="/facts/Group_(mathematics)/IQTYqINt">group</a> called the <a href="/facts/Symmetric_group/RUksK5l5">symmetric group</a> of the set. The <a href="/facts/Group_operation/IQTYqINt">group operation</a> is the <a href="/facts/Function_composition/r5Pvnmth">composition of functions</a> (performing one rearrangement after the other), which results in another function (rearrangement). 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 
 
 
 
 S
 =
 {
 1
 ,
 2
 ,
 …
 ,
 n
 }
 
 
 {\displaystyle S=\{1,2,\ldots ,n\}}
 
.
In elementary combinatorics, the k-permutations, or <a href="/facts/Partial_permutation/dT6tyJfy">partial permutations</a>, are the ordered arrangements of k distinct elements selected from a set. When k is equal to the size of the set, these are the permutations in the previous sense.

Permutation open-in-new

Permutation