Permutation
In mathematics, a permutation is defined as a bijective function from a set to itself, representing a rearrangement of its elements without repetition or omission.[1] Equivalently, it can be viewed as an ordered arrangement of the distinct objects in a finite set, where the order matters in distinguishing one permutation from another.[2] For a set with n elements, the total number of possible permutations is n!, the factorial of n, which quantifies the ways to arrange all elements.[3]
Permutations play a foundational role in combinatorics, where they are used to count ordered selections, such as arranging books on a shelf or scheduling tasks, distinguishing them from combinations by emphasizing sequence.[4] In this context, the number of permutations of k elements selected from n distinct objects, denoted P(n, k), is given by \frac{n!}{(n-k)!}.[5] This counting principle extends to probability and statistics, enabling calculations of event likelihoods in scenarios like lotteries or experimental designs.[6]
In abstract algebra, the collection of all permutations of a set with n elements forms the symmetric group S_n, a non-abelian group under function composition with order n!.[3] Permutations in S_n can be decomposed into disjoint cycles, providing a unique representation up to cycle order, which aids in analyzing group structure and symmetries.[7] Even and odd permutations, determined by the parity of the number of transpositions needed to express them, partition S_n into the alternating group A_n of index 2.[8]
Beyond pure mathematics, permutations underpin applications in computer science for algorithm design, such as sorting networks and cryptographic substitutions, and in physics for modeling particle symmetries in quantum mechanics.[9] They also appear in biology for genome rearrangements and in operations research for optimizing sequences in logistics.[10]
Fundamentals
Definition
In mathematics, a permutation of a set S is a bijection from S to itself, meaning a function \sigma: S \to S that is both injective (one-to-one) and surjective (onto).[3][11] For a finite set S = \{1, 2, \dots, n\}, this corresponds to a rearrangement of its elements, where each element is uniquely mapped to another in the set without omission or repetition.[12] The one-to-one property ensures that distinct elements in S map to distinct elements, while the onto property guarantees every element in S is the image of exactly one element; together, these imply that permutations preserve the cardinality of finite sets, as injectivity shows |S| \leq |S| and surjectivity shows |S| \geq |S|, yielding equality.[3]
Formally, a permutation \sigma of \{1, 2, \dots, n\} satisfies \sigma(i) = j for a unique j corresponding to each i, with the mapping covering all elements exactly once:
\sigma: \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}, \quad \sigma \text{ bijective}.
This bijection can be verified by noting that the inverse \sigma^{-1} exists and is also a bijection, confirming the structure.[12]
The collection of all permutations of an n-element set forms the symmetric group S_n under the operation of function composition, which serves as the group operation.[3] The order of S_n is n!, the number of distinct bijections, derived by choosing any of n elements for the image of 1, then n-1 for 2, and so on down to 1.[11][12]
Examples and Intuition
A permutation rearranges the elements of a set while preserving the set itself. For the set {1, 2, 3}, there are exactly six distinct permutations, which can be listed in one-line notation as follows: 123 (the identity, where each element stays in place), 132 (swapping 2 and 3), 213 (swapping 1 and 2), 231 (cycling 1 to 2, 2 to 3, 3 to 1), 312 (cycling 1 to 3, 3 to 2, 2 to 1), and 321 (reversing the order).[11] These examples illustrate how a permutation acts on positions: for instance, in 231, the element in position 1 moves to position 2, the element in position 2 moves to position 3, and the element in position 3 moves to position 1.
To build intuition, consider permutations as the distinct ways to arrange a set of distinct objects in a sequence, where the order matters. For example, suppose three people—A, B, and C—are to be seated in a row of three chairs. The possible arrangements are ABC, ACB, BAC, BCA, CAB, and CBA, corresponding one-to-one with the permutations of {1, 2, 3} if we label A=1, B=2, C=3. This highlights that permutations capture all unique orderings without regard to rotations or reflections unless specified otherwise.[13]
Visualizing the action of a permutation on positions versus values clarifies its dual nature. In the permutation 231 of {1, 2, 3}:
- Positions: The value in position 1 (originally 1) goes to position 2; position 2 (originally 2) goes to position 3; position 3 (originally 3) goes to position 1.
- Values: 1 is sent to 2, 2 is sent to 3, and 3 is sent to 1.
This can be represented as:
| Position | Original Value | After Permutation (231) |
|---|
| 1 | 1 | 2 |
| 2 | 2 | 3 |
| 3 | 3 | 1 |
Notation
One-line Notation
One-line notation provides a compact representation of a permutation \sigma of the set \{1, 2, \dots, n\} by listing the images \sigma(1), \sigma(2), \dots, \sigma(n) in sequence, typically enclosed in parentheses: (\sigma(1) \ \sigma(2) \ \dots \ \sigma(n)). This notation treats the permutation as a word over the ordered alphabet \{1 < 2 < \dots < n\}, ensuring that each permutation corresponds uniquely to such a sequence without repetition. For example, the permutation that cycles three elements as (1\ 2\ 3) is written in one-line notation as (2\ 3\ 1), indicating \sigma(1)=2, \sigma(2)=3, and \sigma(3)=1.[15][11]
The simplicity of one-line notation makes it particularly useful for enumerating permutations and performing computational tasks, such as generating all permutations of a set in lexicographic order, where sequences are ordered alphabetically based on their one-line representations. For instance, the permutations of \{1, 2, 3\} in lexicographic order begin with (1\ 2\ 3), (1\ 3\ 2), (2\ 1\ 3), and so on. This format is injective, meaning distinct permutations yield distinct notations, and the original permutation can be directly recovered from the sequence.[16][15][17]
To convert an explicit mapping to one-line notation, simply list the images in the order of the domain elements: for \sigma where \sigma(1)=3, \sigma(2)=5, \sigma(3)=4, \sigma(4)=1, and \sigma(5)=2, the notation is (3\ 5\ 4\ 1\ 2). This process is straightforward and highlights the bijection nature of permutations. However, while effective for listing and ordering, one-line notation offers less insight into the cyclic decomposition of the permutation compared to alternatives like cycle notation.[15][11]
Cycle Notation
Cycle notation provides a compact way to represent permutations by decomposing them into cycles, which highlight the structure of how elements are rearranged. A k-cycle is a permutation that cyclically shifts k distinct elements while fixing all others; it is denoted by (a_1 \, a_2 \, \dots \, a_k), meaning the permutation maps a_1 to a_2, a_2 to a_3, ..., a_{k-1} to a_k, and a_k back to a_1.[18] This notation is defined up to cyclic rotation, so (a_1 \, a_2 \, \dots \, a_k) = (a_2 \, \dots \, a_k \, a_1).[18]
Any permutation \sigma of a finite set can be expressed as a product of one or more disjoint cycles, whose supports partition the set.[18] This disjoint cycle decomposition is unique up to the order of the cycles and the starting point within each cycle.[18] To obtain the decomposition, start with an arbitrary element x not yet in a cycle, and follow its orbit under \sigma: compute \sigma(x), \sigma^2(x), and so on until returning to x, forming a cycle; repeat with remaining elements until all are covered. This process yields disjoint cycles because orbits under \sigma partition the set into equivalence classes where two elements are related if one is reachable from the other by repeated application of \sigma.[19][20]
For example, consider the permutation in one-line notation (2 \, 1 \, 3 \, 4), which maps 1 to 2, 2 to 1, 3 to 3, and 4 to 4; its cycle decomposition is (1 \, 2)(3)(4).[1] The identity permutation, which fixes every element, decomposes into a product of all 1-cycles, such as (1)(2)(3)(4) for a set of four elements.[1] Cycles of length 1, known as fixed points, are often omitted in the notation for brevity, so the identity is typically written with no cycles, and the example above simplifies to (1 \, 2).[18][1]
Since disjoint cycles involve distinct elements and thus commute under composition, the permutation is given by \sigma = \prod c_i, where the c_i are the disjoint cycles in the decomposition (with the product order irrelevant).[18][1]
Two-line Notation
Two-line notation represents a permutation \sigma of the set \{1, 2, \dots, n\} by arranging the domain elements $1 to n in the upper row and their corresponding images \sigma(1), \sigma(2), \dots, \sigma(n) in the lower row, often enclosed in parentheses or brackets for clarity./08%3A_Permutations_and_the_Determinant/8.01%3A_Permutations)[21] For example, the permutation that cycles three elements forward is written as
\begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1
\end{pmatrix},
indicating \sigma(1) = 2, \sigma(2) = 3, and \sigma(3) = 1.[22][23]
This notation explicitly displays the bijection from the domain to the codomain, making it particularly useful in formal proofs and early mathematical texts where the full mapping must be evident./08%3A_Permutations_and_the_Determinant/8.01%3A_Permutations)[23] It originated with Augustin-Louis Cauchy in his 1815 memoir on permutations, tying into early developments in function notation for substitutions.[24]
To convert a permutation from one-line notation—which lists only the images \sigma(1) \sigma(2) \dots \sigma(n)—to two-line notation, simply prepend the ordered domain row $1 \, 2 \, \dots \, n above it.[15]
One advantage of two-line notation is its ease in verifying the permutation property: injectivity follows from no repeated entries in the lower row, and surjectivity from the presence of all elements from 1 to n there, allowing quick scans without additional computation./08%3A_Permutations_and_the_Determinant/8.01%3A_Permutations)[23]
Properties
Cycle Structure
Every permutation of a finite set admits a unique decomposition into a product of disjoint cycles, up to the ordering of the cycles and the choice of starting points within each cycle. This uniqueness theorem follows from the fact that the orbits of the cyclic subgroup generated by the permutation partition the set uniquely, with each orbit corresponding to a cycle in the decomposition. To construct the decomposition explicitly, begin with the smallest element not yet included in a cycle, apply the permutation repeatedly until returning to the starting element to form the cycle, then repeat the process with the next smallest unused element until all elements are covered; fixed points (1-cycles) may be omitted in the notation.[25]
The cycle structure of a permutation is determined by its cycle type, which is the partition of n (the size of the set) given by the lengths of the cycles in the decomposition, typically written in decreasing order and including 1-cycles only implicitly. For example, a permutation in S_5 consisting of a 3-cycle and two fixed points has cycle type (3,1,1), corresponding to the partition $3+1+1=5. This type captures the symmetry of the permutation and is invariant under conjugation in the symmetric group.[25]
In the symmetric group S_4, permutations are classified by the following cycle types, each representing a distinct partition of 4:
| Cycle Type | Description | Example |
|---|
| (4) | One 4-cycle | (1 2 3 4) |
| (3,1) | One 3-cycle, one fixed point | (1 2 3) |
| (2,2) | Two 2-cycles | (1 2)(3 4) |
| (2,1,1) | One 2-cycle, two fixed points | (1 2) |
| (1,1,1,1) | Four fixed points (identity) | () |
Order of a Permutation
The order of a permutation \sigma in the symmetric group S_n is defined as the smallest positive integer k such that \sigma^k is the identity permutation.[26]
When a permutation is expressed as a product of disjoint cycles, its order is the least common multiple (LCM) of the lengths of those cycles.[27] This follows because disjoint cycles commute and act independently on their respective supports, so \sigma^k equals the identity if and only if k is a multiple of the length of each cycle; thus, the smallest such k is the LCM of the cycle lengths.[26]
Formally, if \sigma = c_1 c_2 \cdots c_m is the disjoint cycle decomposition of \sigma with \ell_i denoting the length of c_i for each i, then the order of \sigma is \operatorname{lcm}(\ell_1, \ell_2, \dots, \ell_m).[27]
For example, consider the permutation \sigma = (1\ 2\ 3)(4\ 5) in S_5, which decomposes into a 3-cycle and a 2-cycle, so its order is \operatorname{lcm}(3, 2) = 6.[26] To verify, compute the powers: \sigma^1 = (1\ 2\ 3)(4\ 5), \sigma^2 = (1\ 3\ 2)(4)(5), \sigma^3 = (1\ 2\ 3)(4\ 5)^3 = (1)(2)(3)(4\ 5), \sigma^4 = (1\ 3\ 2)(4\ 5), \sigma^5 = (1\ 2\ 3)(4)(5), and \sigma^6 = id. No smaller positive exponent yields the identity.[27]
Parity of a Permutation
A permutation \sigma \in S_n is defined as even if it can be expressed as a product of an even number of transpositions and odd if it can be expressed as a product of an odd number of transpositions.[28][29] The sign function, denoted \operatorname{sign}(\sigma), assigns +1 to even permutations and -1 to odd permutations, formally given by \operatorname{sign}(\sigma) = (-1)^r, where r is the number of transpositions in such a decomposition.[30]
This parity is well-defined, meaning it does not depend on the particular decomposition into transpositions, as any two decompositions of the same permutation into transpositions must have lengths congruent modulo 2.[30] The proof relies on showing that if \sigma equals two products of r and r' transpositions, then r + r' is even, using the fact that the identity permutation cannot be written as an odd number of transpositions.[30]
In terms of cycle decomposition, the sign can be computed as \operatorname{sign}(\sigma) = (-1)^{n - c}, where c is the number of cycles in \sigma (including fixed points of length 1), or equivalently \operatorname{sign}(\sigma) = (-1)^{\sum (l_i - 1)} over the lengths l_i of the cycles.[31][32] This follows because a k-cycle decomposes into k-1 transpositions, so its sign is (-1)^{k-1}, and the overall sign is the product over disjoint cycles.[30][32]
For examples, a transposition (2-cycle) is odd, as it is already one transposition with \operatorname{sign} = -1.[30] A 3-cycle, such as (1\ 2\ 3) = (1\ 2)(2\ 3), decomposes into two transpositions and is thus even with \operatorname{sign} = +1.[30] In S_3, the even permutations are the identity and the two 3-cycles (1\ 2\ 3) and (1\ 3\ 2), while the three transpositions (1\ 2), (1\ 3), and (2\ 3) are odd.[28][29]
The sign function is a group homomorphism from S_n to the multiplicative group \{+1, -1\}, satisfying \operatorname{sign}(\sigma \tau) = \operatorname{sign}(\sigma) \operatorname{sign}(\tau) for all \sigma, \tau \in S_n.[30][31] This multiplicative property holds because the product \sigma \tau decomposes into a number of transpositions equal to the sum of those in \sigma and \tau.[30]
Conjugacy and Cycle Type
In the symmetric group S_n, two permutations \sigma and \tau are conjugate if there exists some \gamma \in S_n such that \tau = \gamma \sigma \gamma^{-1}.[33]
A fundamental theorem states that in S_n, two permutations are conjugate if and only if they have the same cycle type.[33] The cycle type of a permutation is the multiset of the lengths of its disjoint cycles in its cycle decomposition, which corresponds to a partition of n.[33] Thus, the conjugacy classes of S_n are precisely the sets of permutations sharing the same cycle type, and the number of such classes equals p(n), the number of integer partitions of n.[34]
To see why conjugation preserves cycle type, consider a permutation \sigma decomposed into disjoint cycles \sigma = \alpha_1 \alpha_2 \cdots \alpha_\ell, where each \alpha_i is a cycle of length k_i. For any \gamma \in S_n, the conjugate is \gamma \sigma \gamma^{-1} = (\gamma \alpha_1 \gamma^{-1}) (\gamma \alpha_2 \gamma^{-1}) \cdots (\gamma \alpha_\ell \gamma^{-1}). Each \gamma \alpha_i \gamma^{-1} is a cycle of the same length k_i, obtained by applying \gamma to the elements of \alpha_i, and the cycles remain disjoint.[33] Conversely, given two permutations with the same cycle type, one can construct a \gamma that maps the cycles of one to the cycles of the other while preserving lengths, ensuring conjugacy.[33]
For example, in S_4, the cycle type consisting of two disjoint 2-cycles, such as (1\,2)(3\,4), forms a single conjugacy class; all double transpositions are conjugate to each other via suitable relabeling in S_4.[35] The conjugacy classes of S_4 correspond to the partitions of 4: (4), (3,1), (2,2), (2,1,1), and (1,1,1,1).[35]
Permutations in S_n can also be represented as n \times n permutation matrices, which have exactly one 1 in each row and column, with the rest 0s. Two such matrices are similar via conjugation by another permutation matrix if and only if the corresponding permutations have the same cycle type.[36]
Variations
k-Permutations
A k-permutation of a set of n elements is an ordered selection of k distinct elements from the set, where the order of selection matters and no element is repeated. Equivalently, it corresponds to the number of injective functions (one-to-one mappings) from a set of k elements to a set of n elements, ensuring each selected element is uniquely assigned without overlap.[37][38]
The number of such k-permutations, denoted P(n,k), is given by the formula
P(n,k) = \frac{n!}{(n-k)!},
where n! denotes the factorial of n (the product of all positive integers up to n). This arises from the sequential choice process: there are n options for the first position, n-1 for the second, and so on, down to n-k+1 for the k-th position. Thus,
P(n,k) = n \times (n-1) \times \cdots \times (n-k+1).
This product equals \frac{n!}{(n-k)!} because the full factorial n! includes the remaining (n-k) terms in the denominator, which cancel out the unnecessary factors.[38][37]
For example, consider a set {1, 2, 3} with n=3 and k=2. The possible 2-permutations are (1,2), (1,3), (2,1), (2,3), (3,1), and (3,2), totaling P(3,2) = 3 \times 2 = 6. In contrast to combinations, which count unordered selections (e.g., {1,2} is the same regardless of order, yielding C(3,2) = 3), k-permutations distinguish between arrangements like (1,2) and (2,1) as distinct.[39][38]
When k = n, the formula simplifies to P(n,n) = n!, which counts the full permutations of the entire set.[37]
Permutations of Multisets
A permutation of a multiset is a rearrangement of its elements, where the presence of identical elements means that some arrangements are indistinguishable from others. For a multiset consisting of n = \sum_{i=1}^k n_i elements, with n_i identical copies of the i-th type for i = 1, \dots, k, the number of distinct permutations is given by the multinomial coefficient
\binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1! \, n_2! \cdots n_k!}.
This formula arises because there are n! ways to arrange n elements if all were distinct, but for each type i, the n_i! permutations among the identical copies are indistinguishable, so the total is divided by \prod_{i=1}^k n_i!.[40][41]
The derivation can be understood sequentially: first choose n_1 positions out of n for the first type (\binom{n}{n_1}), then n_2 out of the remaining n - n_1 for the second type (\binom{n - n_1}{n_2}), and so on, yielding
\frac{n!}{n_1! (n - n_1)!} \cdot \frac{(n - n_1)!}{n_2! (n - n_1 - n_2)!} \cdots \frac{(n_1 + \cdots + n_{k-1})!}{n_k! \, 0!} = \frac{n!}{n_1! \, n_2! \cdots n_k!}.
This confirms the multinomial coefficient counts the distinct linear arrangements.[41]
For example, consider the multiset \{a, a, b\} with n_1 = 2 for a and n_2 = 1 for b. The number of distinct permutations is \frac{3!}{2! \, 1!} = 3, namely aab, aba, and baa. Similarly, for the multiset corresponding to the letters in "PEPPER" (n_P = 3, n_E = 2, n_R = 1), there are \frac{6!}{3! \, 2! \, 1!} = 60 distinct arrangements.[41]
In combinatorics, permutations of multisets are fundamental for counting distinct objects under symmetry, such as the number of distinct words formed from a given letter multiset or the arrangements of indistinguishable particles in statistical mechanics. These counts also appear in applications like distributing indistinguishable items into distinct bins or enumerating molecular configurations where identical atoms reduce the distinct isomers.[41]
Circular Permutations
Circular permutations refer to arrangements of objects in a circle where rotations of the entire arrangement are considered identical, distinguishing them from linear arrangements by accounting for this rotational symmetry. To count such permutations, one typically fixes the position of a single object to eliminate the redundancy introduced by the n possible rotations, thereby reducing the problem to arranging the remaining n-1 objects in a line relative to the fixed one.[42]
For n distinct objects, the number of circular permutations is given by the formula (n-1)!. This arises from the total number of linear permutations, n!, divided by n to account for the rotational equivalences, yielding n!/n = (n-1)!.[43] For example, arranging 5 distinct people around a circular table results in (5-1)! = 24 distinct arrangements, as fixing one person's position allows the remaining 4 to be seated in 4! ways.[42]
Unlike linear permutations, where all n! arrangements are unique, circular permutations treat rotated versions as the same but do not consider reflections (such as flipping the arrangement) as equivalent unless specified by additional symmetries like the dihedral group. This focus on rotations alone makes circular permutations suitable for scenarios like seating arrangements where directionality (clockwise vs. counterclockwise) is preserved but starting point is irrelevant.[43]
Permutations with Repetition
Permutations with repetition, also known as arrangements with replacement, refer to the ordered selections of k elements from a set of n distinct objects where repetition of elements is permitted.[44] These can be conceptualized as the number of functions from a set of size k (the positions) to a set of size n (the objects), which are not required to be injective.[45] Equivalently, they correspond to the number of words of length k that can be formed from an alphabet of n letters, allowing any letter to appear multiple times.[44]
The total number of such permutations is given by the formula n^k, since there are n choices for each of the k positions, and the choices are independent.[45] This follows from the product rule in combinatorics, where the count multiplies the options at each step without restriction from prior selections.[44]
For example, consider n=2 objects labeled a and b, and k=2 positions. The possible arrangements are aa, ab, ba, and bb, totaling $2^2 = 4.[45]
In contrast to k-permutations without repetition, which require distinct elements and yield \frac{n!}{(n-k)!} arrangements (ensuring bijectivity onto the selected subset), permutations with repetition allow duplicates, resulting in more possible outcomes but non-bijective mappings.[45]
These permutations find practical applications in scenarios involving codes and identifiers where repetition enhances variety without depleting options. For instance, the number of possible 4-digit PIN codes using digits 0-9 (with repetition allowed) is $10^4 = 10,000.[46] Similarly, license plates often employ this principle; a format with 3 letters (A-Z, repeatable) followed by 3 digits (0-9, repeatable) allows $26^3 \times 10^3 = 17,576,000 unique plates.[47]
Combinatorial Aspects
Ascents, Descents, and Inversions
In the context of permutations viewed as sequences, an ascent occurs at position i in a permutation \sigma = (\sigma(1), \sigma(2), \dots, \sigma(n)) if \sigma(i) < \sigma(i+1), while a descent occurs if \sigma(i) > \sigma(i+1).[48] A run is a maximal consecutive subsequence of the permutation that is strictly increasing, so the number of runs in \sigma equals one more than the number of descents.[49]
An inversion in a permutation \sigma is a pair of positions (i, j) with i < j and \sigma(i) > \sigma(j); the inversion number \operatorname{inv}(\sigma) is the total count of such pairs, providing a measure of the permutation's disorder and relating to the complexity of sorting algorithms like bubble sort, where each adjacent swap reduces inversions by one.[50]
The average number of inversions over all permutations in the symmetric group S_n is \frac{n(n-1)}{4}, equivalent to half the maximum possible inversions \binom{n}{2}.[50] The generating function for the number of permutations by inversions is \prod_{k=1}^n \frac{1 - x^k}{1 - x} = \prod_{k=1}^n (1 + x + \cdots + x^{k-1}).[50]
For example, the permutation \sigma = (2, 1, 3) has a descent at position 1 since $2 > 1, an ascent at position 2 since $1 < 3, and one inversion from the pair (1,2) where $2 > 1. The parity of the inversion number determines the sign of the permutation: \operatorname{sgn}(\sigma) = (-1)^{\operatorname{inv}(\sigma)}.[51]
Foata's Transition Lemma
Foata's transition lemma establishes a bijection between the set of all permutations in the symmetric group S_n and the set of permutations obtained by reading the canonical cycle decompositions of the original permutations in a specific order. This bijection, denoted \Phi, maps a permutation \pi to \Phi(\pi) such that the number of cycles in \pi equals the number of left-to-right maxima in \Phi(\pi). A left-to-right maximum in a permutation \sigma = \sigma_1 \sigma_2 \dots \sigma_n is a position i where \sigma_i > \sigma_j for all j < i. The lemma facilitates enumerative comparisons between cycle structures and linear features like records, which relate to ascent and descent patterns in permutations.[52]
The map \Phi is constructed explicitly from the cycle decomposition of \pi. First, write \pi in its disjoint cycle decomposition. For each cycle, rotate it so that the largest element appears first, followed by the subsequent elements in the cycle order (e.g., for cycle (c_1 \, c_2 \, \dots \, c_k) with \max = c_m, the rotated cycle is (c_m \, c_{m+1} \, \dots \, c_k \, c_1 \, \dots \, c_{m-1})). Then, sort the rotated cycles in increasing order of their leading (largest) elements. Finally, concatenate these sorted, rotated cycles to form the one-line notation of \Phi(\pi). This process "transitions" the cycle structure into a linear arrangement where the leading elements of the cycles become the left-to-right maxima. The reverse map starts from a one-line notation \sigma, identifies its left-to-right maxima, and forms cycles by taking each segment from one maximum to the next (excluding the following maximum), prepending the maximum to that segment to create the cycle.[53][54]
The bijection is involutive, meaning \Phi \circ \Phi = \mathrm{id}, which immediately implies it is a bijection since applying the forward and reverse steps recovers the original permutation. This involution property ensures that the distribution of the number of cycles over S_n matches the distribution of the number of left-to-right maxima, a key tool in enumerative combinatorics. While the standard form equates cycle count to left-to-right maxima, variants preserve additional statistics such as the inversion number by adjusting the rotation direction (e.g., using minimal elements instead of maximal).[55][56]
For example, consider the permutation \pi = 231 in one-line notation for n=3, which corresponds to the cycle (1\,2\,3). The maximal element is 3, so rotate to (3\,1\,2). With only one cycle, \Phi(231) = 312. This image has one left-to-right maximum (at position 1, value 3). Applying the reverse to 312: the left-to-right maxima are at position 1 (3), and the remaining segment is 1 2, so the cycle is (3 1 2), recovering \pi. Another example is the identity permutation $123, with cycles (1)(2)(3); each rotated to start with its max (itself), sorted increasingly: (1)(2)(3), \Phi(123) = 123, which has three left-to-right maxima (1,2,3), matching the three cycles.[53]
This lemma was introduced by Dominique Foata in the 1960s as part of his work on algebraic and probabilistic aspects of permutations, and it has become a fundamental tool in enumerative combinatorics for transferring statistics between cycle and linear representations.[57]
Generating Functions and Enumeration
Generating functions provide a powerful framework for enumerating permutations and their refinements by combinatorial statistics, such as cycle structures and inversions. The exponential generating function (EGF) for the total number of permutations in the symmetric group S_n is given by \sum_{n=0}^\infty n! \frac{x^n}{n!} = \frac{1}{1-x}, which counts all labeled bijections on n elements.[58] This reflects the species of permutations as sets of disjoint cycles, where the EGF aligns with the structure of linear orderings on labeled sets.[59]
Refinements of this EGF incorporate statistics like the number of inversions, leading to q-analogs that deform the classical count. The Mahonian numbers T(n,k) count the permutations in S_n with exactly k inversions, and their generating function for fixed n is the q-factorial _q! = \prod_{j=1}^n \frac{1 - q^j}{1 - q} = \sum_{k=0}^{n(n-1)/2} T(n,k) q^k.[60] The corresponding q-analog of the EGF is then \sum_{n=0}^\infty _q! \frac{x^n}{n!}, which specializes to \frac{1}{1-x} at q=1 and tracks inversions across all n.[61] These q-analogs have connections to quantum groups, where classical enumeration at q=1 recovers permutation representations in the limit.[62]
For restricted classes of permutations, ordinary generating functions often arise naturally. A prominent example is derangements, permutations with no fixed points, enumerated by the subfactorial !n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}, which approximates n!/e for large n.[63] This formula derives from the inclusion-exclusion principle: let A_i be the set of permutations fixing i, then the number of derangements is | \bigcap_{i=1}^n A_i^c | = n! - \sum |A_i| + \sum |A_i \cap A_j| - \cdots + (-1)^n | \bigcap A_i |, yielding the series after evaluating the intersections as (n-k)! for k fixed points.[63] The exponential generating function for derangements is \sum_{n=0}^\infty !n \frac{x^n}{n!} = \frac{e^{-x}}{1-x}.[64]
Enumeration by cycle type employs the cycle index polynomial of S_n, defined as Z(S_n; x_1, \dots, x_n) = \frac{1}{n!} \sum_{\sigma \in S_n} \prod_{k=1}^n x_k^{c_k(\sigma)}, where c_k(\sigma) is the number of k-cycles in \sigma.[65] This polynomial encodes the distribution of cycle lengths and serves as the EGF for permutations labeled by cycle type when substituting variables appropriately, such as Z_{\text{perm}}(p_1, p_2, \dots; x) = \prod_{k=1}^\infty \frac{1}{1 - p_k x^k}.[59] For instance, setting all p_k = 1 recovers the basic EGF \frac{1}{1-x}.[59]
Applications
In Group Theory
In group theory, permutations of a finite set of n elements form the symmetric group S_n, which consists of all bijections from the set to itself under composition. This group is generated by the set of all transpositions, the permutations that swap two elements and fix the rest.[66] More specifically, S_n is generated by the adjacent transpositions (i, i+1) for i = 1 to n-1, and it admits a Coxeter presentation \langle s_1, \dots, s_{n-1} \mid s_i^2 = 1, (s_i s_{i+1})^3 = 1, (s_i s_j)^2 = 1 \text{ for } |i-j| > 1 \rangle, where the s_i correspond to these adjacent transpositions.[67]
The alternating group A_n is the kernel of the sign homomorphism \operatorname{sgn}: S_n \to \{\pm 1\}, which maps even permutations to $1 and odd permutations to -1, making A_n the subgroup of all even permutations and a normal subgroup of index 2 in S_n.[68] For n \geq 5, A_n is simple, meaning it has no nontrivial normal subgroups.[68]
Permutation groups act on sets by relabeling elements: for a group G \leq S_n acting on a set X with |X| = n, each g \in G permutes the elements of X via x \mapsto g(x). The orbit-stabilizer theorem relates the size of an orbit \operatorname{Orb}(x) = \{g(x) \mid g \in G\} to the stabilizer \operatorname{Stab}(x) = \{g \in G \mid g(x) = x\} by |G| = |\operatorname{Orb}(x)| \cdot |\operatorname{Stab}(x)|, providing a tool to compute subgroup indices and orbit sizes in permutation actions.[69]
The natural permutation representation of S_n arises from its faithful action on \{1, \dots, n\}, embedding S_n into the general linear group \mathrm{GL}_n(\mathbb{C}) via permutation matrices—monomial matrices with exactly one nonzero entry per row and column, all equal to 1. This yields an isomorphism S_n \cong \{P \in M_n(\mathbb{R}) \mid P \text{ is a [permutation matrix](/page/Permutation_matrix)}\} under matrix multiplication, preserving the group operation.[70]
\begin{equation}
S_n \cong \left{ P \in M_n(\mathbb{R}) ;\middle|; P \text{ permutation matrix} \right}
\end{equation}
In representation theory, the permutation representation decomposes into the trivial representation and the standard representation, with characters of irreducible representations constant on conjugacy classes of S_n, which are parameterized by cycle types (partitions of n); these classes label the irreducibles via Young diagrams. Conjugacy classes thus play a central role in character tables for S_n.[71]
Recent developments in computational group theory leverage permutation representations of S_n for algorithmic purposes, such as the Schreier-Sims algorithm, which constructs a base and strong generating set for a permutation group given generators, enabling efficient order computation and membership testing for subgroups of S_n. Post-2000 refinements, including randomized variants and optimizations for large-degree groups, have extended its practicality in software like GAP and Magma.[72]
In Computing
In computing, permutations are fundamental to algorithms for enumeration, randomization, and optimization. A key operation is ranking and unranking permutations in lexicographic order, which maps a permutation to its unique index (rank) from 0 to n!-1 and vice versa. This is efficiently achieved using the factorial number system (factoradic), where the rank of a permutation σ is computed as the sum over i from 1 to n of (the number of remaining elements smaller than σ(i)) multiplied by (n-i)!. Unranking reverses this process by selecting elements based on factoradic digits to construct the permutation. These O(n^2) time algorithms, with optimizations reaching O(n), enable compact storage and generation of specific permutations without enumerating all.
Permutation generation algorithms produce successive permutations efficiently. Heap's algorithm, introduced in 1963, generates all n! permutations of n elements by performing a minimal number of swaps—specifically, O(1) changes per permutation on average—through recursive swaps of the last element with others in a controlled order. It minimizes data movement compared to naive methods, making it suitable for applications requiring iterative permutation exploration. Recursive backtracking, another common approach, builds permutations incrementally by trying assignments and pruning invalid branches, though it may involve more overhead for full enumeration.
For random permutations, the Knuth shuffle (also known as the Fisher-Yates shuffle) produces a uniformly random permutation in O(n time by iteratively swapping each position i with a random position from i to n-1. This ensures every permutation is equally likely, avoiding biases in naive randomization. It is widely implemented in libraries for tasks like data shuffling in simulations.
Permutations underpin several applications in computing. In sorting, permutation networks—such as Batcher's odd-even mergesort network—use fixed comparator stages to realize any permutation, enabling parallel sorting in O(log^2 n) depth on hardware like systolic arrays. In cryptography, S-boxes function as bijective permutations (e.g., 8-bit to 8-bit mappings in DES) to introduce nonlinearity and diffusion, resisting linear cryptanalysis. In constraint satisfaction problems, permutations model assignment tasks like scheduling, where global constraints ensure bijectivity; solvers like artificial ant colony optimization efficiently navigate the permutation space.[73][74]
Generating all permutations of the symmetric group S_n requires Ω(n!) time due to the output size, but practical algorithms like Heap's achieve O(n) time per permutation amortized, making full enumeration feasible only for small n (e.g., n ≤ 12 on standard hardware). Recent 2020s advances leverage GPUs for parallel generation in specialized contexts, such as permutation testing in genome-wide association studies, achieving speedups of 10-100x over CPU methods by distributing independent permutation computations across thousands of cores.
A representative example is the std::next_permutation function in C++, which transforms a range into the next lexicographic permutation in O(n) time by finding the longest non-increasing suffix, swapping the pivot with the smallest larger successor, and reversing the suffix. Its pseudocode is as follows:
bool next_permutation([iterator](/page/Iterator) first, [iterator](/page/Iterator) last) {
if (first == last) return false;
auto i = last;
if (--i == first) return false;
while (true) {
auto i1 = i;
if (*--i < *i1) {
auto j = last;
while (!(*i < *--j));
std::iter_swap(i, j);
std::reverse(i1, last);
return true;
}
if (i == first) {
std::reverse(first, last);
return false;
}
}
}
bool next_permutation([iterator](/page/Iterator) first, [iterator](/page/Iterator) last) {
if (first == last) return false;
auto i = last;
if (--i == first) return false;
while (true) {
auto i1 = i;
if (*--i < *i1) {
auto j = last;
while (!(*i < *--j));
std::iter_swap(i, j);
std::reverse(i1, last);
return true;
}
if (i == first) {
std::reverse(first, last);
return false;
}
}
}
This implementation, based on the C++ standard, facilitates iterative permutation generation in software.
In Probability and Statistics
In probability theory, a random permutation is drawn uniformly from the symmetric group S_n, where each of the n! possible permutations has equal probability $1/n!. This uniform distribution serves as the foundation for analyzing stochastic properties of permutations, such as cycle structures and fixed points. Under this model, the expected number of inversions—pairs (i, j) with i < j but \sigma(i) > \sigma(j)—is \frac{n(n-1)}{4}, derived via linearity of expectation over indicator variables for each potential pair.[75][76]
The number of fixed points in a random permutation, where \sigma(i) = i, converges in distribution to a Poisson random variable with mean 1 as n \to \infty. Consequently, the probability of at least one fixed point approaches $1 - 1/e \approx 0.632, while the probability of no fixed points—a derangement—tends to $1/e \approx 0.3679. This derangement limit arises from the inclusion-exclusion formula for the number of derangements, !n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}, normalized by n!.[76] Steins method further quantifies this approximation by bounding the total variation distance between the fixed-point distribution and Poisson(1) by $4/n, using exchangeable pairs generated by random transpositions.[76]
Permutation tests leverage the uniform distribution over S_n (or subsets thereof) for nonparametric hypothesis testing, generating the null distribution by reshuffling data or labels while preserving marginals. A seminal application is Fisher's exact test for 2×2 contingency tables, which computes the p-value by enumerating all permutations consistent with fixed row and column totals, assessing independence without parametric assumptions. This exact approach is particularly useful for small samples, where asymptotic approximations like the chi-squared test may fail.[77]
The birthday problem generalizes collision probabilities using permutation counts: the probability of no shared birthdays among n people over d=365 days is the number of injections from n to d, or P(d,n) = d! / (d-n)!, divided by d^n, yielding the collision probability $1 - P(d,n)/d^n. For n \approx \sqrt{2 d \ln 2} \approx 23, this exceeds 0.5, highlighting unexpectedly high collision risks in uniform random assignments.[78]
In modern machine learning, permutations enable feature importance assessment in ensemble methods like random forests. Permutation importance measures the degradation in model accuracy—typically via out-of-bag error—after randomly shuffling a single feature's values in the test set, isolating its marginal contribution while keeping others intact. This technique, developed to mitigate biases in impurity-based measures (e.g., overvaluing high-cardinality features), provides unbiased rankings and has been integrated into libraries like scikit-learn for interpretable predictions.[79]
History
Early Contributions
Early ideas of permutations emerged in ancient civilizations through explorations of systematic arrangements in poetry, divination, and enumeration. In ancient India, around 200 BCE, the scholar Pingala authored the Chandaḥśāstra, a treatise on Sanskrit prosody that introduced the prastara method for listing all possible sequences of short (laghu) and long (guru) syllables in poetic meters. This approach effectively enumerated binary permutations, providing the first known recursive algorithms for counting ordered arrangements without distinguishing between combinations and permutations as separate concepts.[80] Similarly, the Chinese I Ching (Book of Changes), compiled around 1000 BCE with roots in earlier oracle bone inscriptions, generated 64 hexagrams by considering all distinct permutations of six binary lines—solid (yang) or broken (yin)—to represent cosmic patterns and divinatory outcomes. These hexagrams exemplified exhaustive enumeration of linear arrangements, influencing philosophical and probabilistic thought.[81]
Medieval Islamic scholars built upon these foundations by applying ordered selections to number theory, inheritance laws, and geometric designs. Kamal al-Dīn al-Fārisī (1260–1319), a Persian mathematician, advanced combinatorial methods in his studies of amicable numbers and factorization, where he explored systematic arrangements of factors that implicitly involved permutations of numerical components.[82] His work on polygonal numbers and the binomial theorem further touched on ordered selections. Broader Islamic combinatorics, as seen in treatises on magic squares by scholars like al-Būnī (d. 1225), required arranging symbols in grids without row or column repetitions, foreshadowing permutation constraints in puzzle-solving. These efforts emphasized counting distinct configurations for religious and scientific purposes, often without explicit factorial notation.[83]
In the Renaissance, European mathematicians engaged with permutations through linguistic and recreational puzzles. Niccolò Tartaglia (c. 1499–1557), in his encyclopedic General Trattato di Numeri et Misure (1556–1560), examined anagrams as rearrangements of letters, using them to illustrate the enumeration of distinct word forms and combinatorial possibilities in arithmetic contexts. This reflected a growing interest in ordered arrangements for cryptography and poetry. A prominent example highlighting these ideas is the 36 officers problem, posed by Leonhard Euler in 1782, which challenged solvers to arrange 36 officers from six regiments and six ranks into a 6×6 grid such that no rank or regiment repeats in any row or column—effectively seeking two orthogonal Latin squares. While formulated by Euler, the problem echoed earlier roots in Islamic magic square constructions and Chinese lo shu diagrams, underscoring the focus on non-repeating arrangements in pre-modern counting puzzles. These contributions laid informal groundwork for permutation theory, prioritizing practical enumeration over abstract bijections.[84][85]
In the late 18th century, Joseph-Louis Lagrange laid foundational groundwork for the algebraic study of permutations by examining the symmetries inherent in the roots of polynomial equations. In his 1770–1771 work Réflexions sur la résolution algébrique des équations, Lagrange analyzed how permutations of equation roots preserve the equation's form, introducing early notions of symmetry groups to explain the solvability of cubic and quartic equations by radicals. This approach shifted focus from ad hoc solutions to systematic permutations, anticipating group-theoretic structures without fully abstracting them.[86]
Building on this, Paolo Ruffini advanced the theory in 1799 with his Teoria generale delle equazioni, where he attempted to prove the insolubility of the general quintic equation by radicals, employing permutations to classify transformations of roots and distinguishing even and odd permutations based on the number of transpositions. Ruffini's analysis highlighted the alternating group as a key subgroup, though his proof contained gaps and was initially overlooked. In the 1820s, Niels Henrik Abel provided a rigorous proof in his 1824 memoir Mémoire sur les équations algébriques, confirming the quintic's insolubility and solidifying the role of even and odd permutations in determining solvability; this parity distinction became central to understanding permutation groups.[87][88]
Augustin-Louis Cauchy formalized permutations as abstract objects in 1815, in his Mémoire sur le nombre des valeurs qu'une fonction peut acquérir, defining them independently of specific equations and introducing cycle notation to represent permutations compactly, such as (1 2 3) for a 3-cycle. This notation facilitated the study of permutation composition and subgroups, establishing permutation groups as a distinct algebraic domain.[89][90] Concurrently in the 1830s, Évariste Galois integrated permutations into field theory through his 1831 memoir Mémoire sur les conditions de résolubilité des équations par radicaux, where he defined the symmetric group acting on roots and used conjugacy classes to characterize solvability by radicals, linking group structure directly to field extensions.[91]
A pivotal milestone came in the 1850s with Arthur Cayley's work, particularly his 1854 paper On the theory of groups, as depending on the symbolic equation θ^n = 1, which generalized permutation groups into abstract groups generated by permutations, proving every finite group isomorphic to a permutation subgroup and broadening the scope beyond algebraic equations. This abstraction marked the transition to modern group theory.[92]