{"history":[],"article":{"id":"ac2dd038-36b1-47a4-9f53-c050f56593d9","title":"Permutation","slug":"permutation","content":":::summary\n:::\n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), a **permutation** of a [set](https://bliptext.com/articles/set-mathematics) can mean one of two different things:\nAn example of the first meaning is the six permutations (orderings) of the set {1, 2, 3}: written as [tuples](https://bliptext.com/articles/tuple), they are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1).\n[Anagrams](https://bliptext.com/articles/anagram) 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.\nThe study of permutations of [finite sets](https://bliptext.com/articles/finite-set) is an important topic in [combinatorics](https://bliptext.com/articles/combinatorics) and [group theory](https://bliptext.com/articles/group-theory).\nPermutations are used in almost every branch of mathematics and in many other fields of science.\nIn [computer science](https://bliptext.com/articles/computer-science), they are used for analyzing [sorting algorithms](https://bliptext.com/articles/sorting-algorithm); in [quantum physics](https://bliptext.com/articles/quantum-physics), for describing states of particles; and in [biology](https://bliptext.com/articles/biology), for describing [RNA](https://bliptext.com/articles/rna) sequences.\nThe number of permutations of\nn\ndistinct objects is\nn\n[factorial](https://bliptext.com/articles/factorial), usually written as\nn!\n, which means the product of all positive integers less than or equal to\nn\n.\nAccording to the second meaning, a permutation of a [set](https://bliptext.com/articles/set-mathematics)\nS\nis defined as a [bijection](https://bliptext.com/articles/bijection) from\nS\nto itself.\nThat is, it is a [function](https://bliptext.com/articles/function-mathematics) from\nS\nto\nS\nfor which every element occurs exactly once as an [image](https://bliptext.com/articles/image-mathematics) value.\nSuch a function is equivalent to the rearrangement of the elements of\nS\nin which each element i is replaced by the corresponding \\sigma(i).\nFor example, the permutation (3, 1, 2) is described by the function \\sigma defined as\nThe collection of all permutations of a set form a [group](https://bliptext.com/articles/group-mathematics) called the symmetric [group](https://bliptext.com/articles/group-mathematics) of the set.\nThe group operation is the [composition](https://bliptext.com/articles/function-composition) of functions (performing one rearrangement after the other), which results in another function (rearrangement).\nThe 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.\nIn elementary combinatorics, the '''\nk\n-permutations''', or [partial permutations](https://bliptext.com/articles/partial-permutation), are the ordered arrangements of\nk\ndistinct elements selected from a set.\nWhen\nk\nis equal to the size of the set, these are the permutations in the previous sense.\n# [According to the first meaning of permutation, each of the six rows is a different permutation of three distinct balls | upload.wikimedia.org/wikipedia/commons/4/4c/Permutations///RGB.svg]\n# [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. | upload.wikimedia.org/wikipedia/commons/a/a6/Rubik%27s///cube.svg]\n\n# History\nPermutation-like objects called [hexagrams](https://bliptext.com/articles/hexagram-i-ching) were used in China in the [I Ching](https://bliptext.com/articles/i-ching) ([Pinyin](https://bliptext.com/articles/pinyin): Yi Jing) as early as 1000 BC.\nIn Greece, [Plutarch](https://bliptext.com/articles/plutarch) wrote that [Xenocrates](https://bliptext.com/articles/xenocrates) of Chalcedon (396–314 BC) discovered the number of different syllables possible in the Greek language.\nThis would have been the first attempt on record to solve a difficult problem in permutations and combinations.\n[Al-Khalil](https://bliptext.com/articles/al-khalil-ibn-ahmad-al-farahidi) (717–786), an [Arab mathematician](https://bliptext.com/articles/mathematics-in-medieval-islam) and [cryptographer](https://bliptext.com/articles/cryptographer), wrote the Book of Cryptographic Messages.\nIt contains the first use of permutations and combinations, to list all possible [Arabic](https://bliptext.com/articles/arabic-language) words with and without vowels.\nThe rule to determine the number of permutations of n objects was known in Indian culture around 1150 AD. The [Lilavati](https://bliptext.com/articles/lilavati) by the Indian mathematician [Bhāskara II](https://bliptext.com/articles/bh-skara-ii) contains a passage that translates as follows:\nThe 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.\nIn 1677, [Fabian Stedman](https://bliptext.com/articles/fabian-stedman) described factorials when explaining the number of permutations of bells in [change ringing](https://bliptext.com/articles/change-ringing).\nStarting from two bells: \"first, two must be admitted to be varied in two ways\", which he illustrates by showing 1 2 and 2 1.\nHe then explains that with three bells there are \"three times two figures to be produced out of three\" which again is illustrated.\nHis 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\".\nHe then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three.\nEffectively, this is a recursive process.\nHe continues with five bells using the \"casting away\" method and tabulates the resulting 120 combinations.\nAt this point he gives up and remarks:\nNow the nature of these methods is such, that the changes on one number comprehends the changes on all lesser numbers, ...\ninsomuch 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;\nStedman 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.\nA first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, when [Joseph Louis Lagrange](https://bliptext.com/articles/joseph-louis-lagrange), in the study of polynomial equations, observed that properties of the permutations of the [roots](https://bliptext.com/articles/polynomial) of an equation are related to the possibilities to solve it.\nThis line of work ultimately resulted, through the work of [Évariste Galois](https://bliptext.com/articles/variste-galois), in [Galois theory](https://bliptext.com/articles/galois-theory), which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals.\nIn modern mathematics, there are many similar situations in which understanding a problem requires studying certain permutations related to it.\nThe study of permutations as substitutions on n elements led to the notion of group as algebraic structure, through the works of [Cauchy](https://bliptext.com/articles/cauchy) (1815 memoir).\nPermutations played an important role in the [cryptanalysis of the Enigma machine](https://bliptext.com/articles/cryptanalysis-of-the-enigma), a cipher device used by [Nazi Germany](https://bliptext.com/articles/nazi-germany) during [World War II](https://bliptext.com/articles/world-war-ii).\nIn 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](https://bliptext.com/articles/marian-rejewski) to break the German Enigma cipher in turn of years 1932-1933.\n\n# Definition\nIn mathematics texts it is customary to denote permutations using lowercase Greek letters.\nCommonly, either or are used.\nA permutation can be defined as a [bijection](https://bliptext.com/articles/bijection) (an invertible mapping, a one-to-one and onto function) from a set\nS\nto itself: \"\"The [identity permutation](https://bliptext.com/articles/identity-permutation) is defined by for all elements x\\in S, and can be denoted by the number 1, by, or by a single 1-cycle (x).\nThe set of all permutations of a set with n elements forms the [symmetric group](https://bliptext.com/articles/symmetric-group) S_n, where the [group operation](https://bliptext.com/articles/group-operation) is [composition of functions](https://bliptext.com/articles/composition-of-functions).\nThus for two permutations \\sigma and \\tau in the group S_n, their product is defined by: \"\"Composition is usually written without a dot or other sign.\nIn general, composition of two permutations is not [commutative](https://bliptext.com/articles/commutative):\nAs 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.\nAn older viewpoint sees a permutation as an ordered arrangement or list of all the elements of S, called a passive permutation.\nAccording to this definition, all permutations in are passive.\nThis meaning is subtly distinct from how passive (i.e. alias) is used in [Active and passive transformation](https://bliptext.com/articles/active-and-passive-transformation) and elsewhere, which would consider all permutations open to passive interpretation (regardless of whether they are in one-line notation, two-line notation, etc.).\nA permutation \\sigma can be decomposed into one or more disjoint cycles which are the [orbits](https://bliptext.com/articles/orbit-group-theory) of the cyclic group [acting](https://bliptext.com/articles/group-action) on the set S.\nA cycle is found by repeatedly applying the permutation to an element:, where we assume.\nA cycle consisting of k elements is called a k-cycle.\n(See below.)\nA [fixed point](https://bliptext.com/articles/fixed-point-mathematics) of a permutation \\sigma is an element x which is taken to itself, that is \\sigma(x)=x, forming a 1-cycle (\\,x\\,).\nA permutation with no fixed points is called a [derangement](https://bliptext.com/articles/derangement).\nA permutation exchanging two elements (a single 2-cycle) and leaving the others fixed is called a [transposition](https://bliptext.com/articles/transposition-mathematics).\n\n# Notations\nSeveral notations are widely used to represent permutations conveniently.\nCycle notation is a popular choice, as it is compact and shows the permutation's structure clearly.\nThis article will use cycle notation unless otherwise specified.\n\n## Two-line notation\n[Cauchy](https://bliptext.com/articles/augustin-louis-cauchy)'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.\nFor example, the permutation of S = {1, 2, 3, 4, 5, 6} given by the function\"\"can be written as The elements of S may appear in any order in the first row, so this permutation could also be written:\n\n## One-line notation\nIf there is a \"natural\" order for the elements of S, say, then one uses this for the first row of the two-line notation:\nUnder 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.\nCare 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.\nThe one-line notation is also called the [word](https://bliptext.com/articles/word-mathematics) representation.\nThe example above would then be: (It is typical to use commas to separate these entries only if some have two or more digits.)\nThis compact form is common in elementary [combinatorics](https://bliptext.com/articles/combinatorics) and [computer science](https://bliptext.com/articles/computer-science).\nIt is especially useful in applications where the permutations are to be compared as [larger or smaller](https://bliptext.com/articles/partially-ordered-set) using [lexicographic order](https://bliptext.com/articles/lexicographic-order).\n\n## Cycle notation\nCycle notation describes the effect of repeatedly applying the permutation on the elements of the set S, with an orbit being called a cycle.\nThe permutation is written as a list of cycles; since distinct cycles involve [disjoint](https://bliptext.com/articles/disjoint-sets) sets of elements, this is referred to as \"decomposition into [disjoint](https://bliptext.com/articles/disjoint-sets) cycles\".\nTo write down the permutation \\sigma in cycle notation, one proceeds as follows:\nAlso, it is common to omit 1-cycles, since these can be inferred: for any element x in S not appearing in any cycle, one implicitly assumes.\nFollowing the convention of omitting 1-cycles, one may interpret an individual cycle as a permutation which fixes all the elements not in the cycle (a [cyclic permutation](https://bliptext.com/articles/cyclic-permutation) having only one cycle of length greater than 1).\nThen the list of disjoint cycles can be seen as the composition of these cyclic permutations.\nFor 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.\nA convenient feature of cycle notation is that inverting the permutation is given by reversing the order of the elements in each cycle.\nFor example, \"\"\n\n## Canonical cycle notation\nIn some combinatorial contexts it is useful to fix a certain order for the elements in the cycles and of the (disjoint) cycles themselves.\n[Miklós Bóna](https://bliptext.com/articles/mikl-s-b-na) calls the following ordering choices the canonical cycle notation:\nFor example, is a permutation of in canonical cycle notation.\n[Richard Stanley](https://bliptext.com/articles/richard-p-stanley) calls this the \"standard representation\" of a permutation, and Martin Aigner uses \"standard form\".\n[Sergey Kitaev](https://bliptext.com/articles/sergey-kitaev) also uses the \"standard form\" terminology, but reverses both choices; that is, each cycle lists its minimal element first, and the cycles are sorted in decreasing order of their minimal elements.\n\n## Composition of permutations\nThere are two ways to denote the composition of two permutations.\nIn the most common notation, is the function that maps any element x to.\nThe rightmost permutation is applied to the argument first,\nbecause the argument is written to the right of the function.\nA different rule for multiplying permutations comes from writing the argument to the left of the function, so that the leftmost permutation acts first.\nIn this notation, the permutation is often written as an exponent, so σ acting on x is written xσ; then the product is defined by.\nThis article uses the first definition, where the rightmost permutation is applied first.\nThe [function composition](https://bliptext.com/articles/function-composition) operation satisfies the axioms of a [group](https://bliptext.com/articles/group-mathematics).\nIt is [associative](https://bliptext.com/articles/associative-property), meaning, and products of more than two permutations are usually written without parentheses.\nThe composition operation also has an [identity element](https://bliptext.com/articles/identity-element) (the identity permutation \\text{id}), and each permutation \\sigma has an inverse \\sigma^{-1} (its [inverse function](https://bliptext.com/articles/inverse-function)) with.\n\n# Other uses of the term permutation\nThe concept of a permutation as an ordered arrangement admits several generalizations that have been called permutations, especially in older literature.\n\n## k-permutations of n\nIn older literature and elementary textbooks, a k-permutation of n (sometimes called a **[partial permutation](https://bliptext.com/articles/partial-permutation)**, **sequence without repetition**, **variation**, or **arrangement**) means an ordered **arrangement** (list) of a k-element subset of an n-set.\nThe number of such k-permutations (k-arrangements) of n is denoted variously by such symbols as P^n_k, _nP_k, ^n\\!P_k, P_{n,k}, P(n,k), or A^k_n, computed by the formula:\nwhich is 0 when\nk > n\n, and otherwise is equal to\nThe product is well defined without the assumption that n is a non-negative integer, and is of importance outside combinatorics as well; it is known as the [Pochhammer symbol](https://bliptext.com/articles/pochhammer-symbol) (n)_k or as the k-th falling factorial power :\"\"This usage of the term permutation is closely associated with the term [combination](https://bliptext.com/articles/combination) to mean a subset.\nA k-combination of a set S is a k-element subset of S: the elements of a combination are not ordered.\nOrdering the k-combinations of S in all possible ways produces the k-permutations of S.\nThe number of k-combinations of an n-set, C(n,k), is therefore related to the number of k-permutations of n by:\nThese numbers are also known as [binomial coefficients](https://bliptext.com/articles/binomial-coefficient), usually denoted :\"\"\n\n## Permutations with repetition\nOrdered arrangements of k elements of a set S, where repetition is allowed, are called k-tuples.\nThey have sometimes been referred to as **permutations with repetition**, although they are not permutations in the usual sense.\nThey are also called [words](https://bliptext.com/articles/word-mathematics) or [strings](https://bliptext.com/articles/string-computer-science) over the alphabet S.\nIf the set S has n elements, the number of k-tuples over S is n^k.\n\n## Permutations of multisets\nIf M is a finite [multiset](https://bliptext.com/articles/multiset), then a **[multiset](https://bliptext.com/articles/multiset) permutation** is an ordered arrangement of elements of M in which each element appears a number of times equal exactly to its multiplicity in M.\nAn [anagram](https://bliptext.com/articles/anagram) of a word having some repeated letters is an example of a multiset permutation.\nIf the multiplicities of the elements of M (taken in some order) are m_1, m_2, ..., m_l and their sum (that is, the size of M) is n, then the number of multiset permutations of M is given by the [multinomial coefficient](https://bliptext.com/articles/multinomial-coefficient),\nFor example, the number of distinct anagrams of the word MISSISSIPPI is:\nA k-permutation of a multiset M is a sequence of k elements of M in which each element appears a number of times less than or equal to its multiplicity in M (an element's repetition number).\n# [Permutations without repetition on the left, with repetition to their right | upload.wikimedia.org/wikipedia/commons/6/62/Permutations///with///repetition///cropped.svg]\n\n## Circular permutations\nPermutations, when considered as arrangements, are sometimes referred to as linearly ordered arrangements.\nIf, however, the objects are arranged in a circular manner this distinguished ordering is weakened: there is no \"first element\" in the arrangement, as any element can be considered as the start.\nAn arrangement of distinct objects in a circular manner is called a **circular permutation**.\nThese can be formally defined as [equivalence classes](https://bliptext.com/articles/equivalence-classes) of ordinary permutations of these objects, for the [equivalence relation](https://bliptext.com/articles/equivalence-relation) generated by moving the final element of the linear arrangement to its front.\nTwo circular permutations are equivalent if one can be rotated into the other.\nThe following four circular permutations on four letters are considered to be the same.\n1 4 2 3 4 3 2 1 3 4 1 2 2 3 1 4\nThe circular arrangements are to be read counter-clockwise, so the following two are not equivalent since no rotation can bring one to the other.\n1 1 4 3 3 4 2 2\nThere are (n – 1)!\ncircular permutations of a set with n elements.\n\n# Properties\nThe number of permutations of\nn\ndistinct objects is\nn\n!.\nThe number of\nn\n-permutations with\nk\ndisjoint cycles is the signless [Stirling number of the first kind](https://bliptext.com/articles/stirling-number-of-the-first-kind), denoted c(n,k) or.\n\n## Cycle type\nThe cycles (including the fixed points) of a permutation \\sigma of a set with n elements partition that set; so the lengths of these cycles form an [integer partition](https://bliptext.com/articles/integer-partition) of n, which is called the **cycle type** (or sometimes **cycle structure** or **cycle shape**) of \\sigma.\nThere is a \"1\" in the cycle type for every fixed point of \\sigma, a \"2\" for every transposition, and so on.\nThe cycle type of is\nThis may also be written in a more compact form as\n[112231]\n. More precisely, the general form is, where are the numbers of cycles of respective length.\nThe number of permutations of a given cycle type is\nThe number of cycle types of a set with n elements equals the value of the [partition function](https://bliptext.com/articles/partition-function-number-theory) p(n).\n[Polya](https://bliptext.com/articles/p-lya-enumeration-theorem)'s [cycle index](https://bliptext.com/articles/cycle-index) polynomial is a [generating function](https://bliptext.com/articles/generating-function) which counts permutations by their cycle type.\n\n## Conjugating permutations\nIn general, composing permutations written in cycle notation follows no easily described pattern – the cycles of the composition can be different from those being composed.\nHowever the cycle type is preserved in the special case of [conjugating](https://bliptext.com/articles/conjugacy-class) a permutation \\sigma by another permutation \\pi, which means forming the product.\nHere, is the conjugate of \\sigma by \\pi and its cycle notation can be obtained by taking the cycle notation for \\sigma and applying \\pi to all the entries in it.\nIt follows that two permutations are conjugate exactly when they have the same cycle type.\n\n## Order of a permutation\nThe order of a permutation \\sigma is the smallest positive integer m so that.\nIt is the [least common multiple](https://bliptext.com/articles/least-common-multiple) of the lengths of its cycles.\nFor example, the order of is.\n\n## Parity of a permutation\nEvery permutation of a finite set can be expressed as the product of transpositions.\nAlthough many such expressions for a given permutation may exist, either they all contain an even number of transpositions or they all contain an odd number of transpositions.\nThus all permutations can be classified as [even or odd](https://bliptext.com/articles/even-and-odd-permutations) depending on this number.\nThis result can be extended so as to assign a sign, written, to each permutation.\nif \\sigma is even and if \\sigma is odd.\nThen for two permutations \\sigma and \\pi\nIt follows that\nThe sign of a permutation is equal to the determinant of its permutation matrix (below).\n\n## Matrix representation\nA permutation matrix is an n × n matrix that has exactly one entry 1 in each column and in each row, and all other entries are 0.\nThere are several ways to assign a permutation matrix to a permutation of {1, 2, ..., n}.\nOne natural approach is to define L_{\\sigma} to be the [linear transformation](https://bliptext.com/articles/linear-map) of which permutes the [standard basis](https://bliptext.com/articles/standard-basis) by, and define M_{\\sigma} to be its matrix.\nThat is, M_{\\sigma} has its jth column equal to the n × 1 column vector : its (i, j) entry is to 1 if i = σ(j), and 0 otherwise.\nSince composition of linear mappings is described by matrix multiplication, it follows that this construction is compatible with composition of permutations:\".\"For example, the one-line permutations have product, and the corresponding matrices are:\nIt is also common in the literature to find the inverse convention, where a permutation σ is associated to the matrix whose (i, j) entry is 1 if j = σ(i) and is 0 otherwise.\nIn this convention, permutation matrices multiply in the opposite order from permutations, that is,.\nIn this correspondence, permutation matrices act on the right side of the standard 1 \\times n row vectors :.\nThe [Cayley table](https://bliptext.com/articles/cayley-table) on the right shows these matrices for permutations of 3 elements.\n# [Composition of permutations corresponding to a multiplication of permutation matrices. | upload.wikimedia.org/wikipedia/commons/e/e0/Symmetric///group///3%3B///Cayley///table%3B///matrices.svg]\n\n# Permutations of totally ordered sets\nIn some applications, the elements of the set being permuted will be compared with each other.\nThis requires that the set S has a [total order](https://bliptext.com/articles/total-order) so that any two elements can be compared.\nThe set {1, 2, ..., n} with the usual ≤ relation is the most frequently used set in these applications.\nA number of properties of a permutation are directly related to the total ordering of S, considering the permutation written in one-line notation as a sequence.\n\n## Ascents, descents, runs, exceedances, records\nAn ascent of a permutation σ of n is any position i < n where the following value is bigger than the current one.\nThat is, i is an ascent if.\nFor example, the permutation 3452167 has ascents (at positions) 1, 2, 5, and 6.\nSimilarly, a descent is a position i < n with, so every i with 1 \\leq i j\n. If the inequality is not strict (that is,\nσj ≥ j\n), then j is called a weak exceedance. The number of n-permutations with k exceedances coincides with the number of n-permutations with k descents.\nA record or left-to-right maximum of a permutation σ is an element i such that σ(j) < σ(i) for all j < i.\n\n## Foata's transition lemma\n[Foata](https://bliptext.com/articles/dominique-foata)'s fundamental bijection transforms a permutation \\sigma with a given canonical cycle form into the permutation whose one-line notation has the same sequence of elements with parentheses removed.\nFor example:\nHere the first element in each canonical cycle of \\sigma becomes a record (left-to-right maximum) of \\hat\\sigma.\nGiven \\hat\\sigma, one may find its records and insert parentheses to construct the inverse transformation.\nUnderlining the records in the above example:, which allows the reconstruction of the cycles of \\sigma.\nThe following table shows \\hat\\sigma and \\sigma for the six permutations of S = {1, 2, 3}, with the bold text on each side showing the notation used in the bijection: one-line notation for \\hat\\sigma and canonical cycle notation for \\sigma.\nAs a first corollary, the number of n-permutations with exactly k records is equal to the number of n-permutations with exactly k cycles: this last number is the signless [Stirling number of the first kind](https://bliptext.com/articles/stirling-number-of-the-first-kind), c(n, k).\nFurthermore, Foata's mapping takes an n-permutation with k weak exceedances to an n-permutation with\nk − 1\nascents.\nFor example, (2)(31) = 321 has k = 2 weak exceedances (at index 1 and 2), whereas\nhas\nk − 1 = 1\nascent (at index 1; that is, from 2 to 3).\n\n## Inversions\nAn [inversion](https://bliptext.com/articles/inversion-discrete-mathematics) of a permutation σ is a pair\n(i, j)\nof positions where the entries of a permutation are in the opposite order: i < j and.\nThus a descent is an inversion at two adjacent positions.\nFor example,\nhas (i, j) = (1, 3), (2, 3), and (4, 5), where (σ(i), σ(j)) = (2, 1), (3, 1), and (5, 4).\nSometimes an inversion is defined as the pair of values (σ(i), σ(j)); this makes no difference for the number of inversions, and the reverse pair (σ(j), σ(i)) is an inversion in the above sense for the inverse permutation σ−1.\nThe number of inversions is an important measure for the degree to which the entries of a permutation are out of order; it is the same for σ and for σ−1.\nTo bring a permutation with k inversions into order (that is, transform it into the identity permutation), by successively applying (right-multiplication by) [adjacent transpositions](https://bliptext.com/articles/adjacent-transposition), is always possible and requires a sequence of k such operations.\nMoreover, any reasonable choice for the adjacent transpositions will work: it suffices to choose at each step a transposition of i and\ni + 1\nwhere i is a descent of the permutation as modified so far (so that the transposition will remove this particular descent, although it might create other descents).\nThis is so because applying such a transposition reduces the number of inversions by 1; as long as this number is not zero, the permutation is not the identity, so it has at least one descent.\n[Bubble sort](https://bliptext.com/articles/bubble-sort) and [insertion sort](https://bliptext.com/articles/insertion-sort) can be interpreted as particular instances of this procedure to put a sequence into order.\nIncidentally this procedure proves that any permutation σ can be written as a product of adjacent transpositions; for this one may simply reverse any sequence of such transpositions that transforms σ into the identity.\nIn fact, by enumerating all sequences of adjacent transpositions that would transform σ into the identity, one obtains (after reversal) a complete list of all expressions of minimal length writing σ as a product of adjacent transpositions.\nThe number of permutations of n with k inversions is expressed by a [Mahonian number](https://bliptext.com/articles/mahonian-number).\nThis is the coefficient of q^k in the expansion of the product\nThe notation [n]_q!\ndenotes the [q-factorial](https://bliptext.com/articles/q-factorial).\nThis expansion commonly appears in the study of [necklaces](https://bliptext.com/articles/necklace-combinatorics).\nLet such that ij>i\\geq 1, (no repeat condition).\nIn particular, for all generated permutations to be distinct it is not necessary for the p_i values to be distinct.\nIn the process, one gets that and this provides the recursion procedure.\nEXAMPLES: obviously, for \\lambda_2 one has ; to build \\lambda_3 there are only two possibilities for the coset beginnings satisfying the no repeat condition; the choice p_1=p_2=1 leads to.\nTo continue generating S_4 one needs appropriate coset beginnings (satisfying the no repeat condition): there is a convenient choice:, leading to.\nThen, to build \\lambda_5 a convenient choice for the coset beginnings (satisfying the no repeat condition) is, leading to.\nFrom examples above one can inductively go to higher k in a similar way, choosing coset beginnings of S_{k} in S_{k+1}, as follows: for k even choosing all coset beginnings equal to 1 and for k odd choosing coset beginnings equal to.\nWith such choices the \"last\" permutation is for k odd and for k even (k_-=k-1).\nUsing these explicit formulae one can easily compute the permutation of certain index in the counting/generation steps with minimum computation.\nFor this, writing the index in factorial base is useful.\nFor example, the permutation for index is: , yelding finally,.\nBecause multiplying by swap permutation takes short computing time and every new generated permutation requires only one such swap multiplication, this generation procedure is quite efficient.\nMoreover as there is a simple formula, having the last permutation in each S_k can save even more time to go directly to a permutation with certain index in fewer steps than expected as it can be done in blocks of subgroups rather than swap by swap.\n\n## Applications\nPermutations are used in the [interleaver](https://bliptext.com/articles/interleaver) component of the [error detection and correction](https://bliptext.com/articles/error-detection-and-correction) algorithms, such as [turbo codes](https://bliptext.com/articles/turbo-codes), for example [3GPP Long Term Evolution](https://bliptext.com/articles/3gpp-long-term-evolution) mobile telecommunication standard uses these ideas (see 3GPP technical specification 36.212 ).\nSuch applications raise the question of fast generation of permutations satisfying certain desirable properties.\nOne of the methods is based on the [permutation polynomials](https://bliptext.com/articles/permutation-polynomials).\nAlso as a base for optimal hashing in Unique Permutation Hashing.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T17:33:47.483Z","updated_at":"2025-01-25T17:33:47.483Z","search_vector":"'permut':1","search_content":" \n \n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), a **permutation** of a [set](https://bliptext.com/articles/set-mathematics) can mean one of two different things:\nAn example of the first meaning is the six permutations (orderings) of the set {1, 2, 3}: written as [tuples](https://bliptext.com/articles/tuple), they are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1).\n[Anagrams](https://bliptext.com/articles/anagram) 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.\nThe study of permutations of [finite sets](https://bliptext.com/articles/finite-set) is an important topic in [combinatorics](https://bliptext.com/articles/combinatorics) and [group theory](https://bliptext.com/articles/group-theory).\nPermutations are used in almost every branch of mathematics and in many other fields of science.\nIn [computer science](https://bliptext.com/articles/computer-science), they are used for analyzing [sorting algorithms](https://bliptext.com/articles/sorting-algorithm); in [quantum physics](https://bliptext.com/articles/quantum-physics), for describing states of particles; and in [biology](https://bliptext.com/articles/biology), for describing [RNA](https://bliptext.com/articles/rna) sequences.\nThe number of permutations of\nn\ndistinct objects is\nn\n[factorial](https://bliptext.com/articles/factorial), usually written as\nn!\n, which means the product of all positive integers less than or equal to\nn\n.\nAccording to the second meaning, a permutation of a [set](https://bliptext.com/articles/set-mathematics)\nS\nis defined as a [bijection](https://bliptext.com/articles/bijection) from\nS\nto itself.\nThat is, it is a [function](https://bliptext.com/articles/function-mathematics) from\nS\nto\nS\nfor which every element occurs exactly once as an [image](https://bliptext.com/articles/image-mathematics) value.\nSuch a function is equivalent to the rearrangement of the elements of\nS\nin which each element i is replaced by the corresponding \\sigma(i).\nFor example, the permutation (3, 1, 2) is described by the function \\sigma defined as\nThe collection of all permutations of a set form a [group](https://bliptext.com/articles/group-mathematics) called the symmetric [group](https://bliptext.com/articles/group-mathematics) of the set.\nThe group operation is the [composition](https://bliptext.com/articles/function-composition) of functions (performing one rearrangement after the other), which results in another function (rearrangement).\nThe 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.\nIn elementary combinatorics, the '''\nk\n-permutations''', or [partial permutations](https://bliptext.com/articles/partial-permutation), are the ordered arrangements of\nk\ndistinct elements selected from a set.\nWhen\nk\nis equal to the size of the set, these are the permutations in the previous sense.\n# [According to the first meaning of permutation, each of the six rows is a different permutation of three distinct balls | upload.wikimedia.org/wikipedia/commons/4/4c/Permutations///RGB.svg]\n# [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. | upload.wikimedia.org/wikipedia/commons/a/a6/Rubik%27s///cube.svg]\n\n# History\nPermutation-like objects called [hexagrams](https://bliptext.com/articles/hexagram-i-ching) were used in China in the [I Ching](https://bliptext.com/articles/i-ching) ([Pinyin](https://bliptext.com/articles/pinyin): Yi Jing) as early as 1000 BC.\nIn Greece, [Plutarch](https://bliptext.com/articles/plutarch) wrote that [Xenocrates](https://bliptext.com/articles/xenocrates) of Chalcedon (396–314 BC) discovered the number of different syllables possible in the Greek language.\nThis would have been the first attempt on record to solve a difficult problem in permutations and combinations.\n[Al-Khalil](https://bliptext.com/articles/al-khalil-ibn-ahmad-al-farahidi) (717–786), an [Arab mathematician](https://bliptext.com/articles/mathematics-in-medieval-islam) and [cryptographer](https://bliptext.com/articles/cryptographer), wrote the Book of Cryptographic Messages.\nIt contains the first use of permutations and combinations, to list all possible [Arabic](https://bliptext.com/articles/arabic-language) words with and without vowels.\nThe rule to determine the number of permutations of n objects was known in Indian culture around 1150 AD. The [Lilavati](https://bliptext.com/articles/lilavati) by the Indian mathematician [Bhāskara II](https://bliptext.com/articles/bh-skara-ii) contains a passage that translates as follows:\nThe 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.\nIn 1677, [Fabian Stedman](https://bliptext.com/articles/fabian-stedman) described factorials when explaining the number of permutations of bells in [change ringing](https://bliptext.com/articles/change-ringing).\nStarting from two bells: \"first, two must be admitted to be varied in two ways\", which he illustrates by showing 1 2 and 2 1.\nHe then explains that with three bells there are \"three times two figures to be produced out of three\" which again is illustrated.\nHis 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\".\nHe then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three.\nEffectively, this is a recursive process.\nHe continues with five bells using the \"casting away\" method and tabulates the resulting 120 combinations.\nAt this point he gives up and remarks:\nNow the nature of these methods is such, that the changes on one number comprehends the changes on all lesser numbers, ...\ninsomuch 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;\nStedman 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.\nA first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, when [Joseph Louis Lagrange](https://bliptext.com/articles/joseph-louis-lagrange), in the study of polynomial equations, observed that properties of the permutations of the [roots](https://bliptext.com/articles/polynomial) of an equation are related to the possibilities to solve it.\nThis line of work ultimately resulted, through the work of [Évariste Galois](https://bliptext.com/articles/variste-galois), in [Galois theory](https://bliptext.com/articles/galois-theory), which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals.\nIn modern mathematics, there are many similar situations in which understanding a problem requires studying certain permutations related to it.\nThe study of permutations as substitutions on n elements led to the notion of group as algebraic structure, through the works of [Cauchy](https://bliptext.com/articles/cauchy) (1815 memoir).\nPermutations played an important role in the [cryptanalysis of the Enigma machine](https://bliptext.com/articles/cryptanalysis-of-the-enigma), a cipher device used by [Nazi Germany](https://bliptext.com/articles/nazi-germany) during [World War II](https://bliptext.com/articles/world-war-ii).\nIn 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](https://bliptext.com/articles/marian-rejewski) to break the German Enigma cipher in turn of years 1932-1933.\n\n# Definition\nIn mathematics texts it is customary to denote permutations using lowercase Greek letters.\nCommonly, either or are used.\nA permutation can be defined as a [bijection](https://bliptext.com/articles/bijection) (an invertible mapping, a one-to-one and onto function) from a set\nS\nto itself: \"\"The [identity permutation](https://bliptext.com/articles/identity-permutation) is defined by for all elements x\\in S, and can be denoted by the number 1, by, or by a single 1-cycle (x).\nThe set of all permutations of a set with n elements forms the [symmetric group](https://bliptext.com/articles/symmetric-group) S_n, where the [group operation](https://bliptext.com/articles/group-operation) is [composition of functions](https://bliptext.com/articles/composition-of-functions).\nThus for two permutations \\sigma and \\tau in the group S_n, their product is defined by: \"\"Composition is usually written without a dot or other sign.\nIn general, composition of two permutations is not [commutative](https://bliptext.com/articles/commutative):\nAs 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.\nAn older viewpoint sees a permutation as an ordered arrangement or list of all the elements of S, called a passive permutation.\nAccording to this definition, all permutations in are passive.\nThis meaning is subtly distinct from how passive (i.e. alias) is used in [Active and passive transformation](https://bliptext.com/articles/active-and-passive-transformation) and elsewhere, which would consider all permutations open to passive interpretation (regardless of whether they are in one-line notation, two-line notation, etc.).\nA permutation \\sigma can be decomposed into one or more disjoint cycles which are the [orbits](https://bliptext.com/articles/orbit-group-theory) of the cyclic group [acting](https://bliptext.com/articles/group-action) on the set S.\nA cycle is found by repeatedly applying the permutation to an element:, where we assume.\nA cycle consisting of k elements is called a k-cycle.\n(See below.)\nA [fixed point](https://bliptext.com/articles/fixed-point-mathematics) of a permutation \\sigma is an element x which is taken to itself, that is \\sigma(x)=x, forming a 1-cycle (\\,x\\,).\nA permutation with no fixed points is called a [derangement](https://bliptext.com/articles/derangement).\nA permutation exchanging two elements (a single 2-cycle) and leaving the others fixed is called a [transposition](https://bliptext.com/articles/transposition-mathematics).\n\n# Notations\nSeveral notations are widely used to represent permutations conveniently.\nCycle notation is a popular choice, as it is compact and shows the permutation's structure clearly.\nThis article will use cycle notation unless otherwise specified.\n\n## Two-line notation\n[Cauchy](https://bliptext.com/articles/augustin-louis-cauchy)'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.\nFor example, the permutation of S = {1, 2, 3, 4, 5, 6} given by the function\"\"can be written as The elements of S may appear in any order in the first row, so this permutation could also be written:\n\n## One-line notation\nIf there is a \"natural\" order for the elements of S, say, then one uses this for the first row of the two-line notation:\nUnder 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.\nCare 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.\nThe one-line notation is also called the [word](https://bliptext.com/articles/word-mathematics) representation.\nThe example above would then be: (It is typical to use commas to separate these entries only if some have two or more digits.)\nThis compact form is common in elementary [combinatorics](https://bliptext.com/articles/combinatorics) and [computer science](https://bliptext.com/articles/computer-science).\nIt is especially useful in applications where the permutations are to be compared as [larger or smaller](https://bliptext.com/articles/partially-ordered-set) using [lexicographic order](https://bliptext.com/articles/lexicographic-order).\n\n## Cycle notation\nCycle notation describes the effect of repeatedly applying the permutation on the elements of the set S, with an orbit being called a cycle.\nThe permutation is written as a list of cycles; since distinct cycles involve [disjoint](https://bliptext.com/articles/disjoint-sets) sets of elements, this is referred to as \"decomposition into [disjoint](https://bliptext.com/articles/disjoint-sets) cycles\".\nTo write down the permutation \\sigma in cycle notation, one proceeds as follows:\nAlso, it is common to omit 1-cycles, since these can be inferred: for any element x in S not appearing in any cycle, one implicitly assumes.\nFollowing the convention of omitting 1-cycles, one may interpret an individual cycle as a permutation which fixes all the elements not in the cycle (a [cyclic permutation](https://bliptext.com/articles/cyclic-permutation) having only one cycle of length greater than 1).\nThen the list of disjoint cycles can be seen as the composition of these cyclic permutations.\nFor 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.\nA convenient feature of cycle notation is that inverting the permutation is given by reversing the order of the elements in each cycle.\nFor example, \"\"\n\n## Canonical cycle notation\nIn some combinatorial contexts it is useful to fix a certain order for the elements in the cycles and of the (disjoint) cycles themselves.\n[Miklós Bóna](https://bliptext.com/articles/mikl-s-b-na) calls the following ordering choices the canonical cycle notation:\nFor example, is a permutation of in canonical cycle notation.\n[Richard Stanley](https://bliptext.com/articles/richard-p-stanley) calls this the \"standard representation\" of a permutation, and Martin Aigner uses \"standard form\".\n[Sergey Kitaev](https://bliptext.com/articles/sergey-kitaev) also uses the \"standard form\" terminology, but reverses both choices; that is, each cycle lists its minimal element first, and the cycles are sorted in decreasing order of their minimal elements.\n\n## Composition of permutations\nThere are two ways to denote the composition of two permutations.\nIn the most common notation, is the function that maps any element x to.\nThe rightmost permutation is applied to the argument first,\nbecause the argument is written to the right of the function.\nA different rule for multiplying permutations comes from writing the argument to the left of the function, so that the leftmost permutation acts first.\nIn this notation, the permutation is often written as an exponent, so σ acting on x is written xσ; then the product is defined by.\nThis article uses the first definition, where the rightmost permutation is applied first.\nThe [function composition](https://bliptext.com/articles/function-composition) operation satisfies the axioms of a [group](https://bliptext.com/articles/group-mathematics).\nIt is [associative](https://bliptext.com/articles/associative-property), meaning, and products of more than two permutations are usually written without parentheses.\nThe composition operation also has an [identity element](https://bliptext.com/articles/identity-element) (the identity permutation \\text{id}), and each permutation \\sigma has an inverse \\sigma^{-1} (its [inverse function](https://bliptext.com/articles/inverse-function)) with.\n\n# Other uses of the term permutation\nThe concept of a permutation as an ordered arrangement admits several generalizations that have been called permutations, especially in older literature.\n\n## k-permutations of n\nIn older literature and elementary textbooks, a k-permutation of n (sometimes called a **[partial permutation](https://bliptext.com/articles/partial-permutation)**, **sequence without repetition**, **variation**, or **arrangement**) means an ordered **arrangement** (list) of a k-element subset of an n-set.\nThe number of such k-permutations (k-arrangements) of n is denoted variously by such symbols as P^n_k, _nP_k, ^n\\!P_k, P_{n,k}, P(n,k), or A^k_n, computed by the formula:\nwhich is 0 when\nk > n\n, and otherwise is equal to\nThe product is well defined without the assumption that n is a non-negative integer, and is of importance outside combinatorics as well; it is known as the [Pochhammer symbol](https://bliptext.com/articles/pochhammer-symbol) (n)_k or as the k-th falling factorial power :\"\"This usage of the term permutation is closely associated with the term [combination](https://bliptext.com/articles/combination) to mean a subset.\nA k-combination of a set S is a k-element subset of S: the elements of a combination are not ordered.\nOrdering the k-combinations of S in all possible ways produces the k-permutations of S.\nThe number of k-combinations of an n-set, C(n,k), is therefore related to the number of k-permutations of n by:\nThese numbers are also known as [binomial coefficients](https://bliptext.com/articles/binomial-coefficient), usually denoted :\"\"\n\n## Permutations with repetition\nOrdered arrangements of k elements of a set S, where repetition is allowed, are called k-tuples.\nThey have sometimes been referred to as **permutations with repetition**, although they are not permutations in the usual sense.\nThey are also called [words](https://bliptext.com/articles/word-mathematics) or [strings](https://bliptext.com/articles/string-computer-science) over the alphabet S.\nIf the set S has n elements, the number of k-tuples over S is n^k.\n\n## Permutations of multisets\nIf M is a finite [multiset](https://bliptext.com/articles/multiset), then a **[multiset](https://bliptext.com/articles/multiset) permutation** is an ordered arrangement of elements of M in which each element appears a number of times equal exactly to its multiplicity in M.\nAn [anagram](https://bliptext.com/articles/anagram) of a word having some repeated letters is an example of a multiset permutation.\nIf the multiplicities of the elements of M (taken in some order) are m_1, m_2, ..., m_l and their sum (that is, the size of M) is n, then the number of multiset permutations of M is given by the [multinomial coefficient](https://bliptext.com/articles/multinomial-coefficient),\nFor example, the number of distinct anagrams of the word MISSISSIPPI is:\nA k-permutation of a multiset M is a sequence of k elements of M in which each element appears a number of times less than or equal to its multiplicity in M (an element's repetition number).\n# [Permutations without repetition on the left, with repetition to their right | upload.wikimedia.org/wikipedia/commons/6/62/Permutations///with///repetition///cropped.svg]\n\n## Circular permutations\nPermutations, when considered as arrangements, are sometimes referred to as linearly ordered arrangements.\nIf, however, the objects are arranged in a circular manner this distinguished ordering is weakened: there is no \"first element\" in the arrangement, as any element can be considered as the start.\nAn arrangement of distinct objects in a circular manner is called a **circular permutation**.\nThese can be formally defined as [equivalence classes](https://bliptext.com/articles/equivalence-classes) of ordinary permutations of these objects, for the [equivalence relation](https://bliptext.com/articles/equivalence-relation) generated by moving the final element of the linear arrangement to its front.\nTwo circular permutations are equivalent if one can be rotated into the other.\nThe following four circular permutations on four letters are considered to be the same.\n1 4 2 3 4 3 2 1 3 4 1 2 2 3 1 4\nThe circular arrangements are to be read counter-clockwise, so the following two are not equivalent since no rotation can bring one to the other.\n1 1 4 3 3 4 2 2\nThere are (n – 1)!\ncircular permutations of a set with n elements.\n\n# Properties\nThe number of permutations of\nn\ndistinct objects is\nn\n!.\nThe number of\nn\n-permutations with\nk\ndisjoint cycles is the signless [Stirling number of the first kind](https://bliptext.com/articles/stirling-number-of-the-first-kind), denoted c(n,k) or.\n\n## Cycle type\nThe cycles (including the fixed points) of a permutation \\sigma of a set with n elements partition that set; so the lengths of these cycles form an [integer partition](https://bliptext.com/articles/integer-partition) of n, which is called the **cycle type** (or sometimes **cycle structure** or **cycle shape**) of \\sigma.\nThere is a \"1\" in the cycle type for every fixed point of \\sigma, a \"2\" for every transposition, and so on.\nThe cycle type of is\nThis may also be written in a more compact form as\n[112231]\n. More precisely, the general form is, where are the numbers of cycles of respective length.\nThe number of permutations of a given cycle type is\nThe number of cycle types of a set with n elements equals the value of the [partition function](https://bliptext.com/articles/partition-function-number-theory) p(n).\n[Polya](https://bliptext.com/articles/p-lya-enumeration-theorem)'s [cycle index](https://bliptext.com/articles/cycle-index) polynomial is a [generating function](https://bliptext.com/articles/generating-function) which counts permutations by their cycle type.\n\n## Conjugating permutations\nIn general, composing permutations written in cycle notation follows no easily described pattern – the cycles of the composition can be different from those being composed.\nHowever the cycle type is preserved in the special case of [conjugating](https://bliptext.com/articles/conjugacy-class) a permutation \\sigma by another permutation \\pi, which means forming the product.\nHere, is the conjugate of \\sigma by \\pi and its cycle notation can be obtained by taking the cycle notation for \\sigma and applying \\pi to all the entries in it.\nIt follows that two permutations are conjugate exactly when they have the same cycle type.\n\n## Order of a permutation\nThe order of a permutation \\sigma is the smallest positive integer m so that.\nIt is the [least common multiple](https://bliptext.com/articles/least-common-multiple) of the lengths of its cycles.\nFor example, the order of is.\n\n## Parity of a permutation\nEvery permutation of a finite set can be expressed as the product of transpositions.\nAlthough many such expressions for a given permutation may exist, either they all contain an even number of transpositions or they all contain an odd number of transpositions.\nThus all permutations can be classified as [even or odd](https://bliptext.com/articles/even-and-odd-permutations) depending on this number.\nThis result can be extended so as to assign a sign, written, to each permutation.\nif \\sigma is even and if \\sigma is odd.\nThen for two permutations \\sigma and \\pi\nIt follows that\nThe sign of a permutation is equal to the determinant of its permutation matrix (below).\n\n## Matrix representation\nA permutation matrix is an n × n matrix that has exactly one entry 1 in each column and in each row, and all other entries are 0.\nThere are several ways to assign a permutation matrix to a permutation of {1, 2, ..., n}.\nOne natural approach is to define L_{\\sigma} to be the [linear transformation](https://bliptext.com/articles/linear-map) of which permutes the [standard basis](https://bliptext.com/articles/standard-basis) by, and define M_{\\sigma} to be its matrix.\nThat is, M_{\\sigma} has its jth column equal to the n × 1 column vector : its (i, j) entry is to 1 if i = σ(j), and 0 otherwise.\nSince composition of linear mappings is described by matrix multiplication, it follows that this construction is compatible with composition of permutations:\".\"For example, the one-line permutations have product, and the corresponding matrices are:\nIt is also common in the literature to find the inverse convention, where a permutation σ is associated to the matrix whose (i, j) entry is 1 if j = σ(i) and is 0 otherwise.\nIn this convention, permutation matrices multiply in the opposite order from permutations, that is,.\nIn this correspondence, permutation matrices act on the right side of the standard 1 \\times n row vectors :.\nThe [Cayley table](https://bliptext.com/articles/cayley-table) on the right shows these matrices for permutations of 3 elements.\n# [Composition of permutations corresponding to a multiplication of permutation matrices. | upload.wikimedia.org/wikipedia/commons/e/e0/Symmetric///group///3%3B///Cayley///table%3B///matrices.svg]\n\n# Permutations of totally ordered sets\nIn some applications, the elements of the set being permuted will be compared with each other.\nThis requires that the set S has a [total order](https://bliptext.com/articles/total-order) so that any two elements can be compared.\nThe set {1, 2, ..., n} with the usual ≤ relation is the most frequently used set in these applications.\nA number of properties of a permutation are directly related to the total ordering of S, considering the permutation written in one-line notation as a sequence.\n\n## Ascents, descents, runs, exceedances, records\nAn ascent of a permutation σ of n is any position i < n where the following value is bigger than the current one.\nThat is, i is an ascent if.\nFor example, the permutation 3452167 has ascents (at positions) 1, 2, 5, and 6.\nSimilarly, a descent is a position i < n with, so every i with 1 \\leq i j\n. If the inequality is not strict (that is,\nσj ≥ j\n), then j is called a weak exceedance. The number of n-permutations with k exceedances coincides with the number of n-permutations with k descents.\nA record or left-to-right maximum of a permutation σ is an element i such that σ(j) j>i\\geq 1, (no repeat condition).\nIn particular, for all generated permutations to be distinct it is not necessary for the p_i values to be distinct.\nIn the process, one gets that and this provides the recursion procedure.\nEXAMPLES: obviously, for \\lambda_2 one has ; to build \\lambda_3 there are only two possibilities for the coset beginnings satisfying the no repeat condition; the choice p_1=p_2=1 leads to.\nTo continue generating S_4 one needs appropriate coset beginnings (satisfying the no repeat condition): there is a convenient choice:, leading to.\nThen, to build \\lambda_5 a convenient choice for the coset beginnings (satisfying the no repeat condition) is, leading to.\nFrom examples above one can inductively go to higher k in a similar way, choosing coset beginnings of S_{k} in S_{k+1}, as follows: for k even choosing all coset beginnings equal to 1 and for k odd choosing coset beginnings equal to.\nWith such choices the \"last\" permutation is for k odd and for k even (k_-=k-1).\nUsing these explicit formulae one can easily compute the permutation of certain index in the counting/generation steps with minimum computation.\nFor this, writing the index in factorial base is useful.\nFor example, the permutation for index is: , yelding finally,.\nBecause multiplying by swap permutation takes short computing time and every new generated permutation requires only one such swap multiplication, this generation procedure is quite efficient.\nMoreover as there is a simple formula, having the last permutation in each S_k can save even more time to go directly to a permutation with certain index in fewer steps than expected as it can be done in blocks of subgroups rather than swap by swap.\n\n## Applications\nPermutations are used in the [interleaver](https://bliptext.com/articles/interleaver) component of the [error detection and correction](https://bliptext.com/articles/error-detection-and-correction) algorithms, such as [turbo codes](https://bliptext.com/articles/turbo-codes), for example [3GPP Long Term Evolution](https://bliptext.com/articles/3gpp-long-term-evolution) mobile telecommunication standard uses these ideas (see 3GPP technical specification 36.212 ).\nSuch applications raise the question of fast generation of permutations satisfying certain desirable properties.\nOne of the methods is based on the [permutation polynomials](https://bliptext.com/articles/permutation-polynomials).\nAlso as a base for optimal hashing in Unique Permutation Hashing.","revisionCount":0},"hasMore":false,"nextCursor":null}