A permutation of a set is a bijection : every element has exactly one image and every element appears exactly once as an image. For a finite set, a permutation can also be recorded as an ordering of all its elements, once a reference order has been chosen. For three distinct letters , the six orderings are
There are three choices for the first letter, two unused letters for the second, and one for the third. Every path in the tree gives one complete ordering, and every ordering has one such path, so the rule of product gives , a factorial.
Figure 1.
The full choice tree for the six permutations of three distinct letters: three first choices, two second choices, and one third choice
. Details.
Ordering versus mapping. Label the reference positions . An ordering tuple of these labels describes the function ; conversely, reading the images recovers the ordering. For example,
means , , , . Its ordered image list is , whereas its cycle decomposition of a permutation is : starting at , follow its successive images back to . Parentheses in the latter expression encode arrows around a permutation cycle, rather than an image list in reference order. [ref]
The two viewpoints answer different useful questions about the same object. An ordering tells us which object occupies each position; a bijection tells us where each label is sent and allows successive rearrangements through function composition. All permutations of labels form the symmetric group, whose subgroups are permutation groups. The counting viewpoint supplies possibilities, a factorial; the mapping viewpoint reveals how rearrangements combine.
Composition convention. Apply the rightmost permutation first:
For the displayed and the transposition , direct evaluation gives
For instance, , but . Thus function composition of permutations need not be commutative; the omitted labels in these permutation cycles are fixed points.
The identity permutation of a set is the bijection with for every . It is the identity element of the symmetric group: composing it on either side of any permutation leaves that permutation unchanged.
On its one-line notation is and its complete cycle decomposition is . Fixed one-cycles are usually omitted, so the same permutation is often written , or when the underlying set is understood.
Every element is fixed. For a finite set it has no inversions of a permutation, has sign , and is its own inverse. The empty set also has exactly one permutation, its identity, consistent with .
For a bijection , composing with gives , and composing the latter with gives the converse. Every orbit therefore has size one or three: the permutation consists of fixed points and disjoint three-cycles. This applies to an infinite underlying set as well as a finite one, since each individual orbit has at most three elements.
For a permutation of a finite set, the cycle containing is its orbit under the iterates of . Its length is the least positive integer with ; finiteness and invertibility guarantee such a return. Two cycles that meet are the same, because any iterate of a common point belongs to both. Thus the cycles partition the set. In cycle notation, the displayed cycle sends each listed element to the next and the last one back to .
Reverse the first entries of a sequence and leave its suffix unchanged. On a permutation, this is a bijection on positions and is its own inverse: performing the same reversal twice restores the state. The nontrivial moves have . With unit-cost moves, the resulting state graph supports a breadth-first search for a minimum-move solution.
Interleave the two equal halves of an even finite list, placing the first half's next entry before the second half's next entry. With zero-based positions and length , position moves to , and the last position stays fixed. For an index in the first half the new position is ; in the second it is , proving the formula. The least positive period of the whole permutation is the multiplicative order of modulo : equality of the multiplier to one fixes every position, and fixing position one requires that equality. In particular, a 52-entry list has period eight. The empty and two-entry cases are identity permutations with least positive period one.
A cycle sends to , continuing cyclically back from to , and fixes elements outside its support. Products conventionally act from right to left. Every permutation is a product of disjoint cycles, unique up to their ordering and cyclic rotation of each displayed list.
An adjacent transposition exchanges consecutive positions and in a permutation, leaving the others fixed; as a permutation of positions it is . Every permutation can be sorted using adjacent transpositions. Swapping an out-of-order adjacent pair decreases its inversion number by one because its comparisons with every third entry have the same total before and after the swap. Consequently the minimum number of adjacent transpositions needed to sort a permutation is its inversion number. For 312, the route 312, 132, 123 uses two swaps.
The Steinhaus-Johnson-Trotter algorithm lists all permutations so consecutive entries differ by one adjacent transposition. Start at increasing order with an arrow pointing left on each label. A label is mobile if its arrow points to an adjacent smaller label. Swap the largest mobile label in its arrow direction, then reverse the arrows of every larger label; stop when none is mobile. For three labels this gives 123, 132, 312, 321, 231, 213. Recursively, the largest label sweeps across each smaller-label arrangement in alternating directions, visiting every insertion position once. This gives a Gray code on permutations, useful when an objective can be updated cheaply after a local exchange.
The Euler zigzag number counts permutations satisfying . Reversing every inequality gives the same count by replacing each label with . The first values, starting at , are . For the two upward-starting examples are 132 and 231. Their exponential generating function is
This convention fixes the direction of the first inequality; adding both directions for doubles the count.[ref]
With the upward-starting convention, an alternating permutation of has one-line entries satisfying
For , the possibilities are and . Reversing every inequality gives the downward-starting convention; complementing each label by is a bijection between the two conventions.
These permutations are counted by the Euler zigzag numbers for one fixed initial direction. For , counting both directions doubles that count. For lengths zero and one, the inequality condition is vacuous, so the direction classes coincide instead.
Alternating refers to the succession of inequalities, not to membership in the alternating group. For example, is upward alternating but is an odd permutation: it swaps two labels. This distinguishes an order pattern from permutation parity.
The order of a permutation is the least positive integer for which is the identity permutation. If its disjoint permutation cycles have lengths , then
Indeed a point in an -cycle returns exactly after a multiple of steps, so all points return exactly at common multiples. The permutation has order six, while its five moved labels do not by themselves determine its order. The identity permutation has order one.
Write the prime factorization of as , with each a positive power of a distinct prime number. The least such that contains a permutation of order is .
For existence, take disjoint permutation cycles of lengths . Their order of a permutation is the least common multiple of those lengths, namely . For minimality, start with the disjoint cycle decomposition of any permutation of order . Assign each full prime-power factor to one cycle whose length is divisible by it; one exists because the least common multiple of all cycle lengths is . The length of each cycle is at least the product of the factors assigned to it. For integers , , so a product of at least two assigned factors is at least their sum; the assertion is immediate for one factor. Summing over cycles gives at least symbols. In particular an element of order requires at least twelve symbols.
A rearrangement of the numerical digits of a numeral. Two numerals have the same digit permutation class exactly when their digit multisets agree. If they represent numbers of the same length, a leading zero must be disallowed.
A signed permutation on labels is a permutation of the symbols satisfying . It is specified by the list , whose absolute values form a permutation of . For example, specifies , , . There are choices: select an ordinary permutation and an independent sign for each entry. Under composition they form the hyperoctahedral group, acting on a hypercube by permuting coordinate axes and reversing their signs.
With the descent convention, the Eulerian number counts permutations of with exactly positions satisfying . These positions are permutation descents. For , the row is : only 123 has no descent and only 321 has two. Inserting the largest label gives
with and out-of-range entries zero. Of the insertion gaps, preserve descents, while the remaining gaps increase the descent count. Some sources shift the second index by one, so the convention must accompany the symbol.[ref]
A descent of a permutation written in one-line form is a position with . Its descent set and number are
These are adjacent comparisons, unlike inversions of a permutation, which compare arbitrary ordered pairs of positions.
For , the descents occur at positions one and three, since and . The middle comparison is increasing. The identity permutation has no descents, while the reversed order has .
The Eulerian number counts permutations with descents under the stated indexing convention. The major index instead sums their positions; for it is , illustrating a different statistic derived from the same descent set.
The major index of a permutation is the sum of its permutation descent positions:
It uses positions, rather than the values being compared. For , the permutation descents occur at positions one and three, giving , whereas the descent number is two.
The major index has the same distribution over all permutations of elements as the inversion number:
For , the six values give . Individual statistics need not agree: has major index one and two inversions. The shared generating polynomial is a statement about their distribution across the whole symmetric group.[ref]
The Eulerian polynomial packages the Eulerian numbers as
Here counts permutation descents. For example, . In particular , because setting every weight to one counts all permutations. The Eulerian number recurrence gives for . Conventions using multiply this polynomial by .
The unsigned Stirling numbers of the first kind count permutations of labels having exactly disjoint permutation cycles, including fixed points as one-cycles. Their signed version is . Equivalently,
The sign convention must be stated because both versions are standard. For three labels, the unsigned counts for are : two three-cycles, three transpositions with one fixed point, and the identity permutation. This cycle count differs from the Stirling number of the second kind, which counts unordered nonempty blocks without a cyclic order inside each block.
The unsigned Stirling number of the first kind is the number of permutations on labels with disjoint permutation cycles. It satisfies
with impossible indices giving zero. Either label forms its own cycle, or it is inserted immediately after one of the old labels in an existing cycle; deleting reverses either construction. Thus . The same recurrence relation gives the coefficient identity .
For a permutation of ordered distinct values, its Lehmer code has entries . Its zero-based lexicographic order rank is . Each entry chooses among the still unused values; the factorial weights count all completions with a smaller choice at the first differing position.
A cyclic permutation, also called a permutation cycle, sends distinct elements and fixes every element outside this list. Its notation is . For example, is the permutation with image list : all four labels lie on one directed loop. In contrast,
has two separate loops, exchanging with and with . It is a permutation composed of two transpositions, rather than a single cyclic permutation.
Figure 1.
Two permutations on four labels: one cyclic permutation and two disjoint permutation cycles , with arrows showing every image
. Details.
Starting at a different point of the same loop changes the written list but preserves the cyclic permutation: . Reversing the direction generally changes the permutation; it gives the inverse function, here . A transposition is a cyclic permutation of length two; a one-element permutation cycle records a fixed point. In a cycle decomposition of a permutation, one-element permutation cycles are usually omitted, with the underlying set understood.
The beauty of this representation is that repeated rearrangements become motion around independent loops. Applying four times returns every label to its start, while applying twice already does so. Disjoint permutation cycles commute under function composition, since each moves only labels the others fix. On labels, there are cyclic permutations whose single loop contains every label: fix as the first written entry and order the other labels freely, giving a factorial. This is also the count of cyclic orderings; choosing a starting position would otherwise count each loop times. Rotations are identified here, while reversing direction is allowed to give a different cyclic ordering.
Proof outline for decomposition. Starting at any label in a finite set, repeatedly apply the permutation. The pigeonhole principle forces a repeated label. If the first repetition were at a label other than the starting one, its two predecessors would be different labels with the same image, contradicting the injective function property. This produces a permutation cycle returning to the start. Start again at a label not yet visited; the new permutation cycle cannot meet an earlier one, since the bijection gives every label a unique predecessor. Continue until every label belongs to a loop. The resulting cycle decomposition of a permutation is unique up to the order of the disjoint permutation cycles and the starting point written in each one. [ref]
A finitely supported permutation fixes every element outside some finite subset. The finitely supported permutations of are the union of the finite symmetric groups acting on , and hence form a countable set. All permutations of form an uncountable set: independently swapping or fixing each pair injects the power set of into this larger set.
A uniform random permutation of distinct objects gives each of the permutations the same probability. Restricting the order to any fixed subset gives a uniform ordering on that subset. Relative ranks encode such a permutation bijectively by independent choices of an insertion position.
Arrange a uniform random permutation of distinct ordered elements around a circle, and let be the greatest number of consecutive entries that appear in increasing order. Put . Then as .
Let count increasing consecutive blocks of length . Each of the starting positions succeeds with probability , so . For , disjoint blocks have independent relative orders; blocks overlapping with a start displacement are both increasing precisely when their length- union is increasing. Thus
Consequently Markov's inequality gives , while Chebyshev's inequality gives for sufficiently large . The latter uses . Both bounds vanish. These are consecutive cyclic runs; allowing arbitrary skipped entries is a different permutation statistic.
For a uniform random permutation , define as the rank of among , with rank one assigned to the smallest value. Each sequence corresponds to exactly one permutation: insert index in position of the current increasing-value list, then assign the final list the values . The equally likely permutations therefore correspond to the equally likely rank sequences. Consequently the are independent random variables, each with the displayed uniform distribution.
The indicators of successively smaller records are independent and have Bernoulli distributions of parameters . Successively larger records use and have the same laws. For , expectation and variance additivity for independent random variables give and .
For a uniform random permutation of objects, let count its fixed points. Write . Each indicator random variable has expected value , so linearity of expectation gives for every . This average does not require independence: for , fixing two specified objects has probability , greater than the product of their individual probabilities.
For four objects, exact enumeration gives counts for fixed points among the equally likely permutations. Their weighted arithmetic mean is . Exactly three fixed points are impossible: the last object must then also be fixed.
Figure 1.
The fixed point count of a uniform random permutation averaged over all permutations of four objects
. Each card lists . Green entries equal their positions and therefore mark fixed points. The probability mass function on the right counts those cards; its expected value is one. Details.
Choose the fixed objects and derange the remaining . Their count is among equally likely permutations. The inclusion-exclusion principle for proves the displayed law, valid for and zero otherwise. With , it includes the all-fixed case and the impossibility of exactly fixed objects. For fixed , the law tends to , the Poisson distribution of mean one.
In a uniformly random permutation of objects, the cycle containing one specified object has a uniform length on . For length , choose the other objects, arrange their order around the tagged object, and permute all remaining objects. The count is , independent of . Its mean is , while the mean number of other elements in that cycle is .
A permutation with no fixed points. Applying the inclusion-exclusion principle to the events that each element is fixed gives . Therefore , and the alternating-series remainder is at most .
// Destination: foundations-of-mathematics.bigb
The number of derangements of an -element set satisfies , , and the displayed recurrence relation for . Choose the image of a distinguished element, in ways. If those two elements form a two-cycle, removing them leaves choices. Otherwise remove the distinguished element from its longer permutation cycle, leaving a derangement on elements. The inverse operation inserts it immediately before . Thus the two disjoint cases contribute for each .
A cyclic ordering of a finite ground set records its elements around an oriented circle, identifying permutations that differ by rotation. There are such orderings for . A uniformly random permutation induces a uniformly random cyclic ordering.
A cyclic interval of length is the set of consecutive positions in a cyclic ordering. For , there are distinct intervals, one ending at each position. Under a uniformly random permutation, a fixed -set appears as an interval with probability . This is the counting mechanism of the Katona circle method.
A generalised permutation is a finite multiset of ordered pairs, displayed as a two-row array or encoded by a finite-support matrix of nonnegative integer multiplicities . The no-repeated-column condition means every multiplicity is zero or one; entries within either individual row may still repeat.
For a permutation of , an inversion is a pair with . Its number equals the Coxeter length for adjacent transpositions: each adjacent swap changes the count by one, and swapping adjacent descents sorts the permutation in exactly that many steps.
The inversion number of a permutation is
For 3142, the inverted pairs of values are , giving three. The inversion number ranges from zero for increasing order to for decreasing order; it is the minimum number of adjacent transpositions needed to sort the permutation. Its parity gives the sign of a permutation, . The same pair-counting formula defines the word inversion number when repeated symbols are allowed.
A transposition is a permutation that exchanges two elements and fixes every other element. Every transposition has order two.
A transposition is a cyclic permutation of length two.
A product of two transpositions is the identity when they coincide, a three-cycle when their supports meet in one letter, and a product of two disjoint permutation cycles when their supports are disjoint.
A permutation of has bounded displacement if some nonnegative integer satisfies
The same bound works at every position; each individual difference being finite would impose no restriction. Displacement zero gives the identity permutation.
For displacement at most one, every permutation is a collection of disjoint adjacent transpositions and fixed points. To prove this, inspect the smallest position not yet fixed or paired. Its image must be , and the only still available possible preimage of is . Thus these two positions are exchanged; continue inductively. Conversely, any such disjoint collection satisfies the bound. Independently choosing whether to exchange each pair gives an uncountable set of examples.
The inverse function has the same displacement bound: if , then . If two permutations have bounds , their function composition has bound by the triangle inequality. Thus bounded-displacement permutations form a group under function composition.

Ancestors (4)

  1. Combinatorics
  2. Area of mathematics
  3. Mathematics
  4. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (2)

A permutation is a specific arrangement of a set of items or elements. In mathematics, particularly in combinatorics, permutations refer to the different ways in which a subset of objects can be ordered or arranged. For example, if you have a set of three items, say \( \{A, B, C\} \), the possible permutations of these items are: 1. ABC 2. ACB 3. BAC 4. BCA 5. CAB 6.