A permutation is a rearrangement of distinct objects or, more formally, a bijection from a set to itself. For a finite set, these descriptions are equivalent once its elements have been placed in an initial order: the image of each element specifies where it goes, and every element occurs exactly once in the resulting arrangement. Permutations also exist on infinite sets, where the language of bijections is more general than the intuitive picture of rearranging a finite list.
Permutations connect combinatorial counting with the algebraic study of symmetry. They describe the possible orders of objects, the relabeling of vertices in a graph, the interchange of roots of a polynomial, and the movement of entries in a computation. Their decomposition into cycles reveals their internal structure; their classification as even or odd governs signs in determinants; and their composition produces the symmetric groups central to modern algebra. Algorithms for generating, sorting, and sampling permutations make these mathematical structures directly useful in computing and statistics.
Definition and elementary counting
For a set , a permutation is a function that is both one-to-one and onto. Every element has exactly one image, and every element is the image of exactly one element. Thus a permutation neither discards nor duplicates objects. If , an arrangement such as represents the permutation with , , , and . The set of all permutations of is commonly denoted ; for this standard -element set, the usual notation is .
There are choices for the first entry of a permutation, for the second, and successively fewer choices until the last entry is forced. Consequently,
The factorial convention has a direct interpretation: the empty set has exactly one bijection to itself, the empty function. The growth is rapid. There are permutations of five objects, of ten, and of twenty. This growth sharply limits exhaustive searches over arrangements.
Elementary counting sometimes uses “permutation” more broadly for an ordered selection of objects from distinct objects without replacement. Their number is
Such a selection is formally an injection from a -element position set into an -element object set, not necessarily a permutation of the entire object set. An unordered selection instead has possibilities, where the binomial coefficient removes the possible orders of the selected objects.
Repeated symbols require another distinction. If positions contain symbols with multiplicities , where , the number of distinguishable arrangements is
For example, the letters of BANANA admit distinct words. Permuting six individually labeled letter tokens still gives permutations, but interchanging indistinguishable copies does not change the displayed word. The count therefore depends on whether the objects themselves, or only their visible types, are distinguished.
Notation, composition, and inverses
Two-line notation displays a permutation’s domain elements above their images:
When the top row is understood to be , one-line notation records only the bottom row, here . Separators are needed when labels have several digits. One-line notation is especially useful for studying order properties such as increasing subsequences, whereas cycle notation emphasizes repeated application of the function.
Permutations combine by function composition. With the standard convention
the rightmost permutation acts first. For example, if swaps 1 and 2 and swaps 2 and 3, then , while . These products differ, showing that permutation composition is generally not commutative. Some texts use permutations acting on the right and read products in the opposite order, so an explicit convention matters whenever calculations are compared.
The identity permutation satisfies for every element. Each permutation has an inverse , determined by
In two-line notation the inverse is obtained by exchanging the rows and then reordering the columns to restore the standard top row. The inverse of the displayed example has one-line notation . Inversion reverses the order of multiplication:
Integer powers denote repeated composition, with and negative powers defined through the inverse.
A further convention distinguishes rearranging positions from relabeling values. If a list is viewed as a function , the rule
moves the old entry at position to position . The inverse in this formula ensures that applying and then agrees with applying . By contrast, the expression specifies which old entry is read into each new position. Both conventions are useful, but they describe opposite directions of reindexing. This distinction is important in array programming, coordinate transformations, and formulas involving indexed sums.
Cycle decomposition and order
Starting at an element of a finite set and repeatedly applying a permutation produces
Because the set is finite, an element eventually repeats. Bijectivity ensures that the first repetition returns to , rather than entering a loop from outside. The resulting orbit is a cycle, written , meaning that maps to , and maps back to . A one-element cycle is a fixed point.
Every finite permutation decomposes into disjoint cycles. For example,
Disjoint cycles commute because they affect separate elements. Their order in the expression is therefore immaterial, and rotating the entries within a cycle does not change it: . Apart from these freedoms, the decomposition is unique. Fixed points are often omitted, so the underlying set must be known if their number matters.
The cycle lengths determine the order of a permutation, meaning the smallest positive integer for which . Each cycle returns to its starting configuration after a multiple of its length, so the order is the least common multiple of all cycle lengths. The displayed permutation has order . More generally, a -cycle raised to the power splits into cycles, each of length . Thus squaring a 6-cycle produces two 3-cycles, while cubing it produces three transpositions.
An involution is a permutation whose square is the identity. Its cycles have lengths only 1 or 2; a fixed-point-free involution is therefore equivalent to a pairing of the underlying elements. On labeled elements, the number of such pairings is
The denominator removes the ordering of the two elements within each pair and the ordering of the pairs themselves.
For infinite sets, finite cycles need not exhaust the decomposition. A nonperiodic orbit under a bijection is indexed by all integers, not merely by nonnegative integers. Translation on , for example, is one infinite orbit. Every permutation partitions its domain into finite cycles and such doubly infinite orbits. Unlike finite permutations, infinite permutations need not have a finite order.
Transpositions, inversions, and parity
A transposition interchanges two elements and fixes every other element. Transpositions generate all finite permutations because a cycle can be written
A -cycle therefore requires transpositions in this expression. More generally, if a permutation of elements has cycles, including fixed points, its minimum length as a product of arbitrary transpositions is . Each transposition merges two cycles or splits one cycle into two, which supplies the corresponding lower bound.
Although transposition factorizations are not unique, the parity of their lengths is invariant. A permutation is even if it is a product of an even number of transpositions and odd otherwise. Its sign is
For a permutation with cycles,
In particular, a -cycle has sign . For , multiplying by any fixed transposition pairs each even permutation with an odd one, so exactly half of the permutations have each parity.
Parity also has an order-theoretic description. An inversion of a one-line permutation is a pair for which . Writing for their number gives
For example, has the inversions , , and , and is therefore odd. Interchanging adjacent entries changes the inversion count by exactly one, providing a direct explanation for the relationship between inversions and transposition parity.
Adjacent transpositions generate , but they measure a different notion of distance from arbitrary transpositions. The minimum number of adjacent swaps needed to sort a permutation is exactly its inversion count. Thus measures minimum sorting cost when any two positions may be exchanged, whereas measures it when only neighboring positions may be exchanged. These two metrics arise naturally in sorting algorithms and in comparisons between ranked lists.
Symmetric groups, actions, and conjugacy
Under composition, all permutations of a set form a group: composition is associative, an identity exists, and every element has an inverse. For an -element set this is the symmetric group , of order . Any subgroup of a symmetric group is called a permutation group. Such a subgroup can represent the rearrangements preserving a particular structure, rather than all possible rearrangements. Rotations and reflections of a square, for example, induce eight permutations of its four vertices, a small subset of the 24 elements of .
A group action on a set assigns a permutation of to each group element in a way that respects multiplication. Equivalently, it is a homomorphism into . The action is faithful if distinct group elements induce distinct permutations. Cayley’s theorem states that every group has a faithful permutation representation: a group acts on its own elements by left multiplication, . For finite , this embeds it into , although smaller faithful actions may exist.
Conjugation of a permutation corresponds to relabeling:
It preserves cycle lengths. Conversely, two elements of are conjugate precisely when their multisets of cycle lengths agree. These multisets are partitions of . If a cycle type has cycles of length , with , the number of permutations of that type is
The factors account for cyclic rotations within cycles, and for exchanges between cycles of equal length.
The even permutations form the alternating group . It is a normal subgroup of index two in for , because it is the kernel of the sign homomorphism. For , is simple: it has no normal subgroups other than itself and the identity subgroup. This structural fact helps explain the significance of permutations in Galois theory. In particular, the nonsolvability of for underlies the failure of a general formula by radicals for polynomial equations of degree five and above.
Permutation matrices and linear algebra
A permutation can be represented by a matrix acting on coordinate vectors. Fixing the convention
where are the standard basis vectors, defines the permutation matrix . It has a 1 in row , column , and zeros elsewhere. Each row and each column contains exactly one 1. With this convention,
This realizes permutations as invertible linear maps on a coordinate vector space.
A permutation matrix is an orthogonal matrix, since permuting coordinates preserves the usual inner product. Consequently,
Its determinant equals , while its trace equals the number of fixed points. After a suitable reordering of the basis, the matrix separates into blocks corresponding to disjoint cycles. A cycle of length contributes characteristic polynomial ; its complex eigenvalues are the th roots of unity. These facts translate cycle structure into spectral information.
Permutations also index the determinant expansion of an arbitrary matrix:
Each term chooses exactly one entry from each row and column. Omitting the signs defines the permanent, a superficially similar expression with markedly different computational properties. For a matrix of zeros and ones describing allowed pairings between two -element sets, the permanent counts the bijections using only allowed pairings.
In numerical computation, left multiplication by a permutation matrix reorders rows, while right multiplication reorders columns according to the chosen convention. Row permutations are central to pivoting in Gaussian elimination, where changing the order of equations helps avoid unsuitable pivots. Simultaneously permuting rows and columns can expose blocks or improve the organization of sparse computations without changing the underlying linear transformation up to a change of basis.
Permutation matrices also connect discrete arrangements with convex optimization. A doubly stochastic matrix has nonnegative entries and every row and column sum equal to 1. The Birkhoff–von Neumann theorem states that every such matrix is a convex combination of permutation matrices. Thus these discrete matrices are exactly the extreme points of the doubly stochastic polytope, a result fundamental to assignment problems and their linear-programming formulations.
Restricted permutations and enumerative structure
Many counting problems concern permutations satisfying additional conditions. A derangement has no fixed points. If denotes their number, inclusion–exclusion gives
The terms alternately subtract and restore permutations fixing specified subsets of positions. Thus , and approaches . Derangements model assignments in which nobody receives their own object, although extra restrictions on who may receive what require more general methods.
Cycle counts lead to the unsigned Stirling numbers of the first kind, conventionally written : the number of permutations of elements having exactly cycles. They satisfy the recurrence
The new element either forms its own cycle or is inserted after one of the existing elements in a cycle. Their generating identity is
This formula records the entire cycle-count distribution in one polynomial.
Other statistics depend on the linear order of positions rather than on cycles. A descent is a position with . The Eulerian number counts permutations having exactly descents. Inversions have a different generating polynomial:
This follows by inserting the largest entry into a permutation of length : its insertion can create any number from 0 to of new inversions. Such generating functions turn combinatorial constructions into algebraic identities.
A permutation contains a pattern if some subsequence has the same relative order as . For example, entries form a 312 pattern because their relative ranks are largest, smallest, middle. Pattern avoidance restricts these relative configurations without prescribing the actual values. Permutations avoiding any one specified pattern of length three are counted by the Catalan numbers,
A classical algorithmic example is stack sorting: the permutations sortable into increasing order by a single stack are precisely those avoiding 231. This links restricted permutations to trees, parenthesized expressions, and recursive decompositions.
Generation, ranking, and sorting algorithms
Enumerating all permutations requires at least one output operation per permutation, so factorial growth cannot be avoided when the full collection is required. Nevertheless, generation methods differ substantially in ordering, memory use, and the amount of change between successive outputs. Lexicographic order compares sequences at the first differing position. To obtain the next permutation, an algorithm finds the rightmost ascent, exchanges its first entry with the smallest larger entry to its right, and reverses the remaining suffix. This uses constant auxiliary space and at most linear time per step.
Minimal-change algorithms instead arrange that consecutive outputs differ by a small operation. The Steinhaus–Johnson–Trotter algorithm generates permutations using adjacent transpositions. It assigns directions to entries, repeatedly moves the largest entry that can move past a smaller neighbor, and reverses the directions of larger entries after the move. Heap’s algorithm is another classical generator, using a single exchange between consecutive outputs. Such methods are useful when a quantity associated with an arrangement can be updated more cheaply after one swap than recomputed from scratch.
A permutation can also be encoded as an integer. Its Lehmer code has digits
These digits record how many smaller unused values follow each entry. The zero-based lexicographic rank is
This factorial number system gives a bijection between and the integers from 0 through . Unranking reverses the procedure by repeatedly selecting an element from an ordered list of unused labels. Balanced data structures support ranking and unranking in time.
Uniform random generation is achieved by the Fisher–Yates shuffle. For , it chooses an integer uniformly from and exchanges positions and . There are equally probable choice sequences, each producing a different permutation. The algorithm therefore samples uniformly in linear time, provided its random index selections are unbiased.
Sorting reverses the perspective: the input order determines a permutation to be brought to the identity. A comparison-based sorting algorithm needs at least comparisons in the worst case on distinct keys, because a binary decision tree must distinguish possible input orders. This yields the familiar lower bound. Counting inversions can nevertheless be done in time through merge-based methods, without performing every adjacent swap that the inversion count represents.
Random permutations and statistical inference
A uniform random permutation assigns probability to each element of . Its coordinates are individually uniform: for any fixed position , the value is equally likely to be any label. They are not independent, however, because no two positions can receive the same value. This simple example distinguishes uniform marginal distributions from independence and makes permutations a basic model of sampling without replacement.
Let be the number of fixed points. For each position, the indicator of being fixed has expectation , so linearity of expectation gives
For , its variance is also 1. As increases, converges in distribution to a Poisson distribution of mean 1. More generally, if is the number of cycles of length , then
Hence the expected total number of cycles is the harmonic number
For any fixed collection of lengths, the corresponding cycle counts become asymptotically independent Poisson variables with means .
Order statistics of permutations exhibit different scales. If is the inversion count, then
Each pair of positions is equally likely to appear in increasing or decreasing value order, giving the expectation. The variance requires accounting for dependence between comparisons that share a position. After centering and scaling, the inversion count approaches a normal distribution. The longest increasing subsequence has a different asymptotic behavior: its expected length is asymptotic to .
Permutations also provide reference distributions in statistical hypothesis testing. A permutation test recomputes a test statistic over rearrangements of labels permitted by the null model or experimental design. In a randomized two-group experiment with fixed group sizes, for example, the relevant rearrangements correspond to treatment assignments allowed by the randomization scheme. If all allowed assignments are equally likely under the specified null, enumeration gives an exact randomization distribution.
The justification is not merely that labels can be rearranged mechanically. It depends on exchangeability under a null hypothesis or on a known assignment mechanism. Paired observations, blocks, clusters, and serial dependence can require restricted permutations rather than unrestricted shuffling. When complete enumeration is impractical, random sampling of allowed rearrangements approximates the reference distribution. The validity of the procedure rests on the permitted transformation group and the hypothesis being tested.
Historical development and wider applications
Systematic counting of arrangements predates the modern definition of a permutation as a bijection. In seventeenth-century Europe, the combinatorial work of Blaise Pascal, Pierre de Fermat, and Gottfried Wilhelm Leibniz helped establish arrangements and combinations as mathematical subjects. Leibniz’s Dissertatio de arte combinatoria appeared in 1666. These early investigations emphasized enumeration and symbolic combination rather than an abstract algebra of permutations.
The algebraic role of permutations developed through the study of equations. In work published in 1770–1771, Joseph-Louis Lagrange examined how expressions in polynomial roots change when the roots are permuted. Paolo Ruffini and Niels Henrik Abel subsequently contributed to the proof that the general quintic cannot be solved by radicals. Évariste Galois, working around 1830–1832, connected solvability to groups of permutations of roots preserving algebraic relations. Augustin-Louis Cauchy developed important results on substitution groups, and Arthur Cayley’s 1854 work helped articulate groups independently of a particular permutation realization.
In graph theory, a permutation of vertices relabels a graph. It is an automorphism when it preserves adjacency. If a graph has adjacency matrix , and vertex is relabeled , the new adjacency matrix is
Graph isomorphism asks whether two graphs are related by such a relabeling. Permutations also encode candidate solutions to routing problems: an ordering of cities describes a tour in the traveling salesman problem, although cyclic rotation and reversal can make several orderings represent the same tour.
Physical puzzles provide concrete permutation groups. In a sliding-tile puzzle, legal moves impose invariants involving tile order and the blank position, so not every apparent arrangement is reachable. Twisty puzzles similarly restrict the permutations and orientations of pieces. These examples distinguish the full symmetric group of imaginable rearrangements from the subgroup generated by physically allowed moves. Their analysis uses generators, invariants, and composition rather than counting arrangements alone.
In cryptography, a block cipher with a fixed key acts as a permutation of fixed-length bit strings: decryption requires each ciphertext block to have a unique corresponding plaintext block. Modern security requirements concern how these keyed permutations behave computationally, not merely whether they are bijections. In machine learning and scientific computing, permutation symmetry instead concerns arbitrary indexing. A permutation-invariant function gives the same output after reordering its inputs, while a permutation-equivariant function changes its output by the corresponding reordering. These properties are essential when representing sets, graphs, particles, or other systems whose labels carry no intrinsic meaning.