Permutation ($\sigma :S\to S\text{ bijective}$)

A permutation of a set $S$ is a bijection $\sigma :S\to S$: 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 $A,B,C$, the six orderings areThere 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 $3\cdot 2\cdot 1=3!=6$, a factorial.

Ordering versus mapping. Label the reference positions $1,\dots ,n$. An ordering tuple $(a_1,\dots ,a_n)$ of these labels describes the function $\sigma (i)=a_i$; conversely, reading the images $\sigma (1),\dots ,\sigma (n)$ recovers the ordering. For example,means $1\mapsto 3$, $2\mapsto 1$, $3\mapsto 4$, $4\mapsto 2$. Its ordered image list is $(3,1,4,2)$, whereas its cycle decomposition of a permutation is $(1342)$: starting at $1$, follow its successive images back to $1$. 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 $n$ labels form the symmetric group, whose subgroups are permutation groups. The counting viewpoint supplies $n!$ possibilities, a factorial; the mapping viewpoint reveals how rearrangements combine.

Composition convention. Apply the rightmost permutation first:For the displayed $\sigma =(1342)$ and the transposition $\tau =(12)$, direct evaluation givesFor instance, $(\sigma \tau )(1)=\sigma (2)=1$, but $(\tau \sigma )(1)=\tau (3)=3$. Thus function composition of permutations need not be commutative; the omitted labels in these permutation cycles are fixed points.

For a bijection $f$, composing $f^2=f^{-1}$ with $f$ gives $f^3=\mathrm{id}$, and composing the latter with $f^{-1}$ 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 $\sigma$ of a finite set, the cycle containing $x$ is its orbit under the iterates of $\sigma$. Its length $k$ is the least positive integer with ${\sigma }^{k}x=x$; 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 $x$.

Reverse the first $k$ 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 $2\le k\le n$. 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 $n>2$, position $i<n-1$ moves to $2i\mathrm{mod}(n-1)$, and the last position stays fixed. For an index in the first half the new position is $2i$; in the second it is $2i-(n-1)$, proving the formula. The least positive period of the whole permutation is the multiplicative order of $2$ modulo $n-1$: 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 $(a_1{a}_2\dots a_k)$ sends $a_1$ to $a_2$, continuing cyclically back from $a_k$ to $a_1$, 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.

Write the prime factorization of $m>1$ as $m=q_1\cdots q_t$, with each $q_j$ a positive power of a distinct prime number. The least $n$ such that $S_n$ contains a permutation of order $m$ is $q_1+\cdots +q_t$.

For existence, take disjoint permutation cycles of lengths $q_j$. Their order of a permutation is the least common multiple of those lengths, namely $m$. For minimality, start with the disjoint cycle decomposition of any permutation of order $m$. Assign each full prime-power factor $q_j$ to one cycle whose length is divisible by it; one exists because the least common multiple of all cycle lengths is $m$. The length of each cycle is at least the product of the factors assigned to it. For integers $a,b\ge 2$, $ab\ge a+b$, 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 ${\sum }_j{q}_j$ symbols. In particular an element of order $60=4\cdot 3\cdot 5$ 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.

For a permutation $p_0,\dots ,p_{n-1}$ of $n$ ordered distinct values, its Lehmer code has entries $c_i=\#\{j>i:p_j<p_i\}$. Its zero-based lexicographic order rank is ${\sum }_{i=0}^{n-1}{c}_i(n-1-i)!$. 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 $k\ge 1$ distinct elements $a_1\mapsto a_2\mapsto \cdots \mapsto a_k\mapsto a_1$ and fixes every element outside this list. Its notation is $(a_1{a}_2\dots a_k)$. For example, $(1342)$ is the permutation with image list $(3,1,4,2)$: all four labels lie on one directed loop. In contrast,has two separate loops, exchanging $1$ with $3$ and $2$ with $4$. It is a permutation composed of two transpositions, rather than a single cyclic permutation.

Starting at a different point of the same loop changes the written list but preserves the cyclic permutation: $(1342)=(3421)$. Reversing the direction generally changes the permutation; it gives the inverse function, here $(1243)$. 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 $(1342)$ four times returns every label to its start, while applying $(13)(24)$ twice already does so. Disjoint permutation cycles commute under function composition, since each moves only labels the others fix. On $n\ge 1$ labels, there are $(n-1)!$ cyclic permutations whose single loop contains every label: fix $1$ as the first written entry and order the other $n-1$ labels freely, giving a factorial. This is also the count of cyclic orderings; choosing a starting position would otherwise count each loop $n$ 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 $\mathbb{N}$ are the union of the finite symmetric groups acting on $\{1,\dots ,k\}$, and hence form a countable set. All permutations of $\mathbb{N}$ form an uncountable set: independently swapping or fixing each pair $(2j-1,2j)$ injects the power set of $\mathbb{N}$ into this larger set.

A uniform random permutation of $n$ distinct objects gives each of the $n!$ 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 $n$ distinct ordered elements around a circle, and let $L$ be the greatest number of consecutive entries that appear in increasing order. Put $k_0=\min \{k:k!\ge n\}$. Then $\mathbb{P}(k_0-2\le L\le k_0)\to 1$ as $n\to \infty$.

Let $X_k$ count increasing consecutive blocks of length $k$. Each of the $n$ starting positions succeeds with probability $1/k!$, so $\mathbb{E}{X}_k=n/k!$. For $k\le n/2$, disjoint blocks have independent relative orders; blocks overlapping with a start displacement $s<k$ are both increasing precisely when their length-$k+s$ union is increasing. ThusConsequently Markov's inequality gives $\mathbb{P}(L\ge k_0+1)\le 1/(k_0+1)$, while Chebyshev's inequality gives $\mathbb{P}(L<k_0-2)\le 2/(k_0-1)$ for sufficiently large $n$. The latter uses $n/(k_0-2)!>k_0-1$. Both bounds vanish. These are consecutive cyclic runs; allowing arbitrary skipped entries is a different permutation statistic.

For a uniform random permutation $a_1,\dots ,a_n$, define $R_i$ as the rank of $a_i$ among $a_1,\dots ,a_i$, with rank one assigned to the smallest value. Each sequence $r_i\in \{1,\dots ,i\}$ corresponds to exactly one permutation: insert index $i$ in position $r_i$ of the current increasing-value list, then assign the final list the values $1,\dots ,n$. The $n!$ equally likely permutations therefore correspond to the ${\prod }_{i=1}^{n}i=n!$ equally likely rank sequences. Consequently the $R_i$ are independent random variables, each with the displayed uniform distribution.

The indicators $Y_i=1_{\{R_i=1\}}$ of successively smaller records are independent and have Bernoulli distributions of parameters $1/i$. Successively larger records use $R_i=i$ and have the same laws. For $K_n={\sum }_{i=1}^n{Y}_i$, expectation and variance additivity for independent random variables give $E{K}_n={\sum }_{i=1}^{n}1/i$ and $\mathrm{Var}{K}_n={\sum }_{i=1}^n(1/i-1/i^2)$.

For a uniform random permutation $\pi$ of $n\ge 1$ objects, let $M_n$ count its fixed points. Write $M_n={\sum }_{i=1}^n{1}_{\{\pi (i)=i\}}$. Each indicator random variable has expected value $1/n$, so linearity of expectation gives $\mathbb{E}[M_n]=1$ for every $n\ge 1$. This average does not require independence: for $n\ge 2$, fixing two specified objects has probability $1/[n(n-1)]$, greater than the product $1/n^2$ of their individual probabilities.

For four objects, exact enumeration gives counts $9,8,6,0,1$ for $0,1,2,3,4$ fixed points among the $24$ equally likely permutations. Their weighted arithmetic mean is $(0\cdot 9+1\cdot 8+2\cdot 6+4\cdot 1)/24=1$. Exactly three fixed points are impossible: the last object must then also be fixed.

Choose the $m$ fixed objects and derange the remaining $n-m$. Their count is $\left(\genfrac{}{}{0ex}{}{n}{m}\right)D_{n-m}$ among $n!$ equally likely permutations. The inclusion-exclusion principle for $D_{n-m}$ proves the displayed law, valid for $0\le m\le n$ and zero otherwise. With $D_0=1$, it includes the all-fixed case and the impossibility of exactly $n-1$ fixed objects. For fixed $m$, the law tends to $e^{-1}/m!$, the Poisson distribution of mean one.

In a uniformly random permutation of $N$ objects, the cycle containing one specified object has a uniform length on $\{1,\dots ,N\}$. For length $\ell$, choose the other $\ell -1$ objects, arrange their order around the tagged object, and permute all remaining objects. The count is $\left(\genfrac{}{}{0ex}{}{N-1}{\ell -1}\right)(\ell -1)!(N-\ell )!=(N-1)!$, independent of $\ell$. Its mean is $(N+1)/2$, while the mean number of other elements in that cycle is $(N-1)/2$.

A permutation with no fixed points. Applying the inclusion-exclusion principle to the events that each element is fixed gives $D_n=n!{\sum }_{k=0}^n(-1{)}^k/k!$. Therefore $D_n/n!\to e^{-1}$, and the alternating-series remainder is at most $1/(n+1)!$.

// Destination: foundations-of-mathematics.bigb

The number $d_n$ of derangements of an $n$-element set satisfies $d_0=1$, $d_1=0$, $d_2=1$ and the displayed recurrence relation for $n\ge 2$. Choose the image $j$ of a distinguished element, in $n-1$ ways. If those two elements form a two-cycle, removing them leaves $d_{n-2}$ choices. Otherwise remove the distinguished element from its longer permutation cycle, leaving a derangement on $n-1$ elements. The inverse operation inserts it immediately before $j$. Thus the two disjoint cases contribute $d_{n-2}+d_{n-1}$ for each $j$.

A cyclic ordering of a finite ground set records its elements around an oriented circle, identifying permutations that differ by rotation. There are $(n-1)!$ such orderings for $n\ge 1$. A uniformly random permutation induces a uniformly random cyclic ordering.

A cyclic interval of length $r$ is the set of $r$ consecutive positions in a cyclic ordering. For $1\le r<n$, there are $n$ distinct intervals, one ending at each position. Under a uniformly random permutation, a fixed $r$-set appears as an interval with probability $n/\left(\genfrac{}{}{0ex}{}{n}{r}\right)$. 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 $m_{a,b}$. The no-repeated-column condition means every multiplicity is zero or one; entries within either individual row may still repeat.

For a permutation $\pi$ of $\{1,\dots ,n\}$, an inversion is a pair $i<j$ with $\pi (i)>\pi (j)$. 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.

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 $\sigma$ of $\mathbb{N}$ has displacement at most one when $|\sigma (j)-j|\le 1$. Such a permutation is a disjoint collection of fixed points and adjacent transpositions, so independently swapping the pairs $(2n-1,2n)$ already gives uncountably many examples.