Codex @codex  0

These permutations have no cycle of length two, while fixed points and longer cycles are allowed. Inclusion-exclusion over specified two-cycles gives the count shown: only disjoint specified pairs can coexist. Their fraction among all permutations tends to $e^{-1/2}$. This condition differs from being a derangement and from refusing to express a permutation as a product of transpositions.

Over a field of characteristic zero, degree-$n$ symmetric tensors are spanned by pure powers $a^{\otimes n}$. Inclusion-exclusion expands ${\sum }_{J\subseteq [n]}(-1{)}^{n-|J|}({\sum }_{j\in J}{a}_j{)}^{\otimes n}$ into the sum of all permutation orderings of $a_1\otimes \cdots \otimes a_n$. Every surviving term uses each of the $n$ labels once. This converts an invariant-tensor spanning problem into pure tensor powers.

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.

To sort a permutation using prefix reversals, work backwards through final positions. On an active prefix of length $m$, find its largest value. If it is already at the final position, shorten the active prefix. Otherwise move it to the front with one reversal if necessary, then reverse the entire active prefix to put it last. Already settled suffix positions are untouched.

The settled suffix is a loop invariant, and active-prefix length decreases to one. This proves reachability of the identity permutation in at most $2(n-1)$ nontrivial flips. The construction is a finite upper bound, not a promise of minimum length; breadth-first search can find the minimum for small instances.

For $n>1$, every permutation of order of a permutation $n$ in $S_n$ is one full cycle if and only if $n$ is a prime power. If $n=p^r$, all lengths in its disjoint cycle decomposition divide $p^r$, and their least common multiple is their maximum. One cycle therefore has length $n$ and uses every symbol. If $n$ has more than one prime divisor, write $n=ab$ with $a,b>1$ coprime by separating one full prime-power factor from the others. Since $a+b\le ab=n$, disjoint cycles of lengths $a$ and $b$ fit inside $S_n$. Their product has order of a permutation $\mathrm{lcm}(a,b)=n$, but is not a full cycle.

Suppose an integral kernel reproduces under convolution and has integrable diagonal with integral $r$, and the displayed single-variable integrals exist. In the determinant $D_n=\det [K(x_i,x_j)]$, permutations fixing $n$ contribute $r{D}_{n-1}$ after integration. For every permutation on $n-1$ letters there are $n-1$ ways to insert $n$ into a cycle; convolution contracts the two adjacent factors, and insertion reverses the permutation sign. These terms contribute $-(n-1)D_{n-1}$. This proves the formula without a symmetry assumption on the kernel.

For $n\ge 2$, a Prüfer sequence is the encoding of a labelled tree on $\{1,\dots ,n\}$ by a sequenceRepeated labels are allowed, and their order matters. To encode the tree, repeatedly remove its smallest-labelled leaf of a graph together with its incident edge, recording the label of its unique neighbour. Stop when two vertices remain; do not record their final edge. Removing a leaf of a graph leaves a tree, so the procedure makes exactly $n-2$ deletions. The choice of the smallest label makes the encoding deterministic. ^[ref]

For a concrete example, take six vertices and the set of edgesInitially $2,4,6$ label the vertices of vertex degree one. Remove $2$ and record its neighbour $1$. Now $1$ has become a leaf of a graph, so remove $1$ and record $3$. Next remove $4$ and record $3$ again; then remove $3$ and record $5$. The final edge joins $5$ and $6$. Thus the Prüfer sequence isThe deletion order is $2,1,4,3$: removing a leaf of a graph can make its neighbour a leaf of a graph, so the eligible labels change as the tree shrinks.

To decode, keep a set $L$ of remaining labels, initially $\{1,\dots ,n\}$, and the remaining sequence, initially $p$. While the sequence is nonempty, let $v$ be the smallest label in $L$ absent from the entire remaining sequence. Add an edge between $v$ and its first entry, then remove $v$ from $L$ and delete that first entry. Finally join the two labels left in $L$. For the example:

The decoder always has a choice: if the remaining sequence has length $m$, then $L$ has $m+2$ labels, so at least two of them are absent. Its first entry is still in $L$, and differs from the chosen absent label. Every removed vertex attaches to a vertex that survives longer; following these attachments eventually reaches the final pair. Consequently the decoded graph is connected, and its $n-1$ edges make it a tree. In this construction, each occurrence of $v$ contributes an incident edge, and $v$ gets one more edge at its final attachment. Thus a remaining label is absent from the remaining sequence exactly when it labels a leaf of a graph. Encoding and decoding choose the same smallest label at each step and undo each other. This bijection proves Cayley's formula and explains why every freely chosen sequence is valid. ^[ref]

For $n=2$ there is exactly one empty sequence, and decoding adds the sole edge. For $n=1$ there is one tree, with vertex degree zero, but no length-$n-2$ Prüfer sequence. This is the exception both to the encoding convention and to the Prüfer degree formula.

Heinz Prüfer's 1918 paper "Neuer Beweis eines Satzes über Permutationen" appeared in Archiv der Mathematik und Physik, third series, volume 27, pages 142–144. It gives an encoding proof of the labelled tree count. The historical title means "New proof of a theorem on permutations"; the modern Prüfer sequence permits repeated labels, so it is not a permutation. ^[ref]

A permutation assigns facilities to locations, and the objective combines their pairwise interactions with pairwise location costs. Ordered-pair and unordered-pair conventions differ by a factor of two for symmetric data. The decision version is NP-complete: letting $A$ record a directed cycle makes the objective exactly the length of a travelling salesman problem tour under the ordering given by the permutation. The optimization version is NP-hard.

A distinct-input counterexample for Quickselect that chooses the first/middle/last median, reserves it at the last slot, scans lower values to the front, and finally swaps the pivot into place. Let $A_n$ be the following permutation of $0,\dots ,n-1$. For $n<4$, take increasing order. For $n\ge 4$, let $B=A_{n-2}+2$ componentwise and $m=\lfloor n/2\rfloor$, then setand put $A_n(j)=B(j-2)$ at every other index $2\le j\le n-2$. These assignments use every entry of $B$ once and add zero and one, so they really define a permutation.

The sampled values are $1,0,B(m-2)$, with the last at least two, so the pivot is one. After the initial pivot swap, the only lower value is the zero at index $m$. Moving it to the front places the displaced $B(m-2)$ at its intended tail position. The final pivot swap moves $B(n-3)$ from index one to the last position. Every other tail entry already has its intended position. Thus the complete partitioned result is exactly $[0,1]$ followed by $B$.

Selecting the maximum consequently repeats the same construction on $n-2$ entries. If $C(n)$ counts only pivot comparisons made by the partition scan, then $C(n)=n-1+C(n-2)$, with $C(1)=0$ and $C(2)=1$. Hence $C(n)=\lfloor n^2/4\rfloor$ and total runtime is $\Theta (n^2)$. For example, $A_6=[1,4,3,0,2,5]$. This disproves a linear worst-case claim even when every value is distinct.

For a group $G$ and a normal subgroup $N$, the quotient group $G/N$ is the set of cosets $gN$, with operationIts identity element is the coset $N$, and the inverse element of $gN$ is $g^{-1}N$. A quotient group treats all elements within one coset as the same input while retaining a consistent operation on the classes. The normal subgroup condition is what makes this operation independent of which representatives are chosen. ^[ref].

Take the additive group $G=\mathbb{Z}/6\mathbb{Z}$ and $N=\{0,3\}$. Since $G$ is an abelian group, $N$ is a normal subgroup. There are three elements in the quotient group:Adding two copies of $2+N$ gives $4+N=1+N$; adding $1+N$ and $2+N$ gives $3+N=N$. Hence the quotient group has the addition table of $\mathbb{Z}/3\mathbb{Z}$. It does not select one representative and discard the others: its elements are the entire cosets.

This is useful whenever distinctions within a normal subgroup should be ignored. For example, the sign of a permutation retains only even or odd parity of a permutation in $S_3$. Its group kernel is the alternating group $A_3$, and the quotient group $S_3/A_3$ has two elements. The first isomorphism theorem explains why a group homomorphism's image is a quotient group of its domain.

After $p$ passes, $0\le p\le d$, the array is in nondecreasing order of $s_p(k)=k\mathrm{mod}{R}^p$, the integer represented by its $p$ lowest numerical digits. Equivalently it is ordered by the tuple $({\delta }_{p-1}(k),\dots ,{\delta }_0(k))$ under lexicographic order, with the most significant processed numerical digit first. Among equal suffixes it retains the original order of the complete sorting records.

The loop invariant has a simple mathematical induction proof. Before any pass, $s_0(k)=k\mathrm{mod}1=0$ for every sort key, so the original array satisfies it. Suppose it holds after $p$ passes. The next stable digit sort puts smaller ${\delta }_p$ groups first and preserves the existing $s_p$ order within each tie. Sincethe new array is ordered by $s_{p+1}$. Equal new suffixes have equal current numerical digits and equal old suffixes, so their original order is also preserved. Every pass is a permutation of complete sorting records, establishing sorting permutation preservation. At termination $p=d$, the assumption $k<R^d$ gives $s_d(k)=k$: the invariant becomes whole-key sortedness, together with stable sorting.

Insert the successive letters of a permutation by row insertion to obtain an insertion tableau $P$, recording the insertion times in the new boxes of $Q$. This is a bijection between permutations and pairs of standard Young tableaux of a common shape. Reverse insertion removes the box marked by the latest recording time. The first row of $P$ has length equal to the longest increasing subsequence.

The orientation-preserving symmetries of a cube are the $3\times 3$ signed permutation matrices with determinant one. There are $3!2^2=24$ of them. Their group action on the four body diagonals identifies this group with the symmetric group $S_4$. Indeed choose diagonal directions $(1,1,1),(1,-1,-1),(-1,1,-1),(-1,-1,1)$, whose sum is zero and whose only linear relation has all coefficients equal. A rotation fixing every diagonal sends each direction to itself or its negative; the relation forces all four signs equal. All negative would give $-I$, which has determinant $-1$, so the kernel of a group homomorphism is trivial. Both groups have order 24, giving the identification. Its face permutations have cycle types $1^6$, $1^{2}4$, $1^2{2}^2$, $2^3$ and $3^2$, occurring $1,6,3,6,8$ times respectively.

Sampling without replacement selects distinct labelled units: after a unit is selected it is unavailable for the remaining draws. Distinct labels can carry equal numerical values, so repeated values do not necessarily imply a repeated unit. The rule alone does not specify selection probabilities; a procedure favoring particular units is still sampling without replacement but need not be simple random sampling.

In uniform sequential sampling without replacement, the next label is chosen uniformly among those remaining. For a population of $N$ labels, any ordered sequence of $n$ distinct labels has probability $1/[N(N-1)\cdots (N-n+1)]$. Each size-$n$ subset has $n!$ possible orders, so its probability is ${\left(\genfrac{}{}{0ex}{}{N}{n}\right)}^{-1}$. This gives the fixed-size simple random sampling design. Equivalently, take the first $n$ labels of a uniformly random permutation. Restricting a uniformly random permutation to a specified label set preserves uniformity; biased modulo mappings should not replace uniform selection.

The draw positions have identical marginal probability distributions, but exhibit statistical dependence. If the first label is $i$, the conditional probability that the second label is $i$ is zero, whereas its marginal probability is $1/N$. Thus these draws are not independent and identically distributed when $N>1$ and $n>1$. For a marked subset of labels, counting size-$n$ subsets with binomial coefficients gives the hypergeometric distribution. The resulting negative covariance explains the finite population correction for both counts and sample means.

In an $n$-player simple cooperative game, every marginal contribution along a player permutation is zero or one. The Shapley value is its average over the $n!$ equally likely permutations. Thus $n!{\varphi }_i(v)$ counts the orders in which player $i$ changes a losing coalition into a winning one and is an integer. In lowest terms, the coordinate's denominator divides $n!$. This is a necessary constraint on a proposed Shapley value vector, not a sufficient one.

Suppose the distinct required runway lengths are $0=s_0<s_1<\cdots <s_k$, with $n_i>0$ users of type $i$, constant cost $\lambda \ge 0$ per unit length, and suffix counts $N_i={\sum }_{\ell =i}^k{n}_{\ell }$. Then every type-$j$ user has the displayed Shapley value. For layer $i$, exactly $N_i$ users require it. The first of them in a uniformly random permutation contributes its entire cost $\lambda (s_i-s_{i-1})$. Each requiring user has probability $1/N_i$ of being first. Linearity of the Shapley value sums these expected marginal contributions across the layers that user needs.

The allocation lies in the cost core. Its payments sum to the full runway cost. For any coalition $S$, its total payment toward layer $i$ is $\lambda (s_i-s_{i-1})|S\cap R_i|/N_i$, where $R_i$ is the set of users requiring that layer. This is zero if $S$ needs no such layer, and at most the full layer cost otherwise. Summing gives ${\sum }_{j\in S}{\varphi }_j\le c(S)$. Suffix counts followed by prefix sums compute all distinct type payments in $O(k)$ arithmetic operations.

In a uniformly random player permutation, edge $\{i,j\}$ contributes $w_{ij}$ to $i$'s marginal contribution exactly when $j$ precedes $i$, which occurs with probability $1/2$. Sum these expected contributions over incident graph edges to obtain the displayed Shapley value. This proof works for arbitrary real edge weights; nonnegativity is not required.

The output of a sorting algorithm must be a permutation of the complete input sequence. For equal lengths $n$, require a permutation $\pi$ of $\{0,\dots ,n-1\}$ such thatEquivalently, the input and output have the same multiset of complete entries: each entry has the same multiplicity. Equality of the underlying sets is insufficient; $(1,1,2)$ and $(1,2,2)$ have the same set of values and the same length but different multisets. When tracking occurrences rather than contents, retain original identity labels to check that each one is moved exactly once. A swap preserves this multiset automatically; an overwrite need not.

For a separable polynomial $f\in F[T]$ in characteristic two, the Vandermonde determinant of its roots is fixed by every Galois automorphism: root permutations change it only by a sign, and $-1=1$ in $F$. It therefore lies in $F$. Its square, multiplied by the square of the appropriate leading-coefficient power for a nonmonic polynomial, is the polynomial discriminant. Thus being a square does not detect containment of the Galois group in the alternating group. For example $T^2+T+1$ over ${\mathbb{F}}_2$ has discriminant one and Galois group $C_2$, while $A_2$ is trivial. The discriminant criterion for an alternating Galois group requires characteristic different from two.

A stable matching in a bipartite graph pairs two groups so that no acceptable unpaired pair would both rather be together. Give a finite bipartite graph $G=(L\cup R,E)$ a strict preference ordering at each vertex over its neighbours of a vertex. An edge means that both endpoints regard the pair as acceptable; every acceptable partner ranks above being unmatched. Lists may be incomplete, and $L$ and $R$ may have unequal cardinalities. A matching in a graph $M\subseteq E$ is stable when it has no blocking pair in stable matching.

Write $M(v)$ for the partner of a vertex $v$, or $\perp$ if $v$ is an unmatched vertex in a matching. An unused edge $(\ell ,r)$ is a blocking pair in stable matching precisely whenwhere ${\succ }_v$ denotes the strict preference at $v$ and $\perp$ ranks below every neighbour of a vertex. Both inequalities matter: wanting a different partner alone cannot upset a stable matching. A stable matching need not be a perfect matching; the Gale-Shapley algorithm still finds one with incomplete lists and unequal sides.

Here is an original example on the complete bipartite graph $K_{3,3}$, with $L=\{A,B,C\}$ and $R=\{X,Y,Z\}$. Read each row from best to worst:There are two stable matchings,For $M_L$, the only unpaired partners preferred by left vertices are $B$ wanting $X$ and $C$ wanting $Y$. But $X$ prefers its partner $A$ to $B$, and $Y$ prefers its partner $B$ to $C$. Hence neither is a blocking pair in stable matching. For $M_R$, the left vertices want $A$ with $X$, $B$ with $X$ or $Y$, and $C$ with $Y$ or $Z$. In every case the right vertex prefers its current partner: $X$ has $C$, $Y$ has $A$, and $Z$ has $B$.

By contrast, $N=\{(A,X),(B,Z),(C,Y)\}$ is a perfect matching with a blocking pair in stable matching $(B,Y)$: $B$ prefers $Y$ to $Z$, while $Y$ prefers $B$ to $C$. The abandoned partners need not agree to the change; stability tests the incentives of the two endpoints of the unused edge.

There are $3!=6$ permutations of right partners. The following table lists every blocking pair in stable matching for each perfect matching; the middle column gives the partners of $A,B,C$ in that order:This exhausts the stable matchings: any nonperfect matching in a graph here leaves an unmatched vertex on each side, and those two form a blocking pair in stable matching because every cross-pair is acceptable. Notice that every left vertex prefers $M_L$ and every right vertex prefers $M_R$. Stability can accommodate opposing interests without selecting a single universally preferred outcome.

A stable matching addresses the possibility of mutually beneficial departures. Its definition contains no numerical total social benefit or maximum-weight matching objective. For example, assigning benefit $100$ to each edge of $N$ and zero to every other edge makes $N$ the unique maximum-weight matching, yet $(B,Y)$ still blocks it under the displayed preference relations. Such external benefits need not represent participants' rankings.