Inversion (discrete mathematics)
An inversion of a finite sequence records a pair of entries whose relative order is opposite to their natural order. For a permutation (\pi\in S_n), written in one-line notation as [ \pi=\pi_1\pi_2\cdots\pi_n, ] an inversion is a pair of indices ((i,j)) satisfying [ 1\leq i<j\leq n \qquad\text{and}\qquad \pi_i>\pi_j. ] The set of all such pairs is the inversion set [ \operatorname{Inv}(\pi) ={(i,j):i<j\text{ and }\pi_i>\pi_j}, ] and its cardinality is the inversion number [ \operatorname{inv}(\pi)=|\operatorname{Inv}(\pi)|. ]
Inversions provide a local description of how far a permutation departs from increasing order. They connect the combinatorics of permutations with sorting, permutation parity, Coxeter groups, (q)-analogues, and rank-correlation statistics. Despite the terminology, the concept is unrelated to geometric inversion and matrix inversion; those operations merely share its habit of making an established order reconsider its position.
Definition and elementary structure
The identity permutation (12\cdots n) has no inversions. The reverse permutation [ n(n-1)\cdots 21 ] has the maximum possible inversion number, [ \binom n2=\frac{n(n-1)}2, ] because every pair of positions forms an inversion. Consequently, [ 0\leq \operatorname{inv}(\pi)\leq \binom n2 ] for every (\pi\in S_n).
For example, the permutation (3142) has the inversion set [ {(1,2),(1,4),(3,4)}, ] and therefore has inversion number (3). The pair ((2,3)) is not an inversion because (1<4), even though the corresponding positions are adjacent. Adjacency concerns the positions of entries, whereas inversion status concerns their relative numerical order.
Replacing every value (\pi_i) by (n+1-\pi_i) reverses the comparison attached to each pair of positions. If (\pi^{\mathrm c}) denotes the resulting complementary permutation, then [ \operatorname{inv}(\pi^{\mathrm c}) =\binom n2-\operatorname{inv}(\pi). ] This involution accounts for the symmetry of the distribution of inversion numbers.
Historical development
In Genroku-period Japan, You Watanabe compiled permutation tables organized by the number of crossed order relations and expressed their successive columns through insertion of a new greatest entry. In modern notation, the resulting recurrence is the coefficient recurrence obtained from multiplication by [ 1+q+\cdots+q^{n-1}. ] The work treated inversion number as a statistic on arrangements rather than as a property of a particular sorting procedure.
During the development of enumerative combinatorics in the late nineteenth and early twentieth centuries, Percy Alexander MacMahon systematically studied the distribution of inversion number and related permutation statistics. The resulting coefficient sequence is called the Mahonian distribution, distinguishing it from the Eulerian distribution, which counts permutations according to their descents. The two statistics are equidistributed only in limited senses and encode different structural information.
Adjacent transpositions and parity
An adjacent transposition exchanges entries in consecutive positions. Such an exchange changes the inversion number by exactly (1): it increases the count when the exchanged entries were in increasing order and decreases it when they were in decreasing order. It follows that the minimum number of adjacent transpositions required to transform (\pi) into the identity is [ \operatorname{inv}(\pi). ]
This interpretation identifies inversion number with the Coxeter length of a permutation in the symmetric group, whose standard generators are the adjacent transpositions [ s_i=(i,i+1). ] A reduced expression for (\pi) contains exactly (\operatorname{inv}(\pi)) generators, although a permutation can have many distinct reduced expressions.
Because each adjacent transposition reverses permutation parity, [ \operatorname{sgn}(\pi)=(-1)^{\operatorname{inv}(\pi)}. ] Thus a permutation is even precisely when its inversion number is even. The full inversion number depends on the chosen linear order, while its parity agrees with the intrinsic sign homomorphism (S_n\to{-1,1}).
The adjacent-transposition interpretation also induces the weak order of permutations. Under a fixed left-or-right convention, a covering relation corresponds to multiplying by an adjacent transposition that increases Coxeter length by one. Inclusion relations among the corresponding inversion sets then encode the order structure.
Generating function
Let [ M(n,k)=|{\pi\in S_n:\operatorname{inv}(\pi)=k}|. ] Inserting the largest element (n) into a permutation of (S_{n-1}) creates between (0) and (n-1) new inversions, depending on its position. This decomposition gives [ M(n,k)=\sum_{j=0}^{n-1}M(n-1,k-j), ] where coefficients outside their natural range are zero.
Equivalently, the inversion-number generating function is [ \sum_{\pi\in S_n}q^{\operatorname{inv}(\pi)} =\prod_{r=1}^{n}(1+q+\cdots+q^{r-1}) =[n]_q!, ] the (q)-factorial. The coefficient of (q^k) in this product is (M(n,k)). Its palindromic form follows from the complement involution: [ M(n,k)=M\left(n,\binom n2-k\right). ]
At (q=1), the generating function reduces to (n!), the total number of permutations. At (q=-1), it records the difference between the numbers of even and odd permutations; this difference vanishes for (n\geq2).
Probabilistic behavior
For a uniformly random permutation (\Pi\in S_n), the inversion number can be written as a sum of indicator variables: [ \operatorname{inv}(\Pi) =\sum_{1\leq i<j\leq n} \mathbf 1_{{\Pi_i>\Pi_j}}. ] Each pair is inverted with probability (1/2), so linearity of expectation gives [ \mathbb E[\operatorname{inv}(\Pi)] =\frac12\binom n2 =\frac{n(n-1)}4. ] The dependence among overlapping pairs contributes to the variance [ \operatorname{Var}(\operatorname{inv}(\Pi)) =\frac{n(n-1)(2n+5)}{72}. ]
After centering by its mean and scaling by its standard deviation, the inversion number converges in distribution to the normal distribution as (n) tends to infinity. This asymptotic behavior can be derived from the representation of inversion number by bounded inversion-sequence coordinates.
Inversion sequences and permutation codes
A permutation can be encoded by recording, for each position, how many earlier entries exceed the current entry. With [ e_i=|{j<i:\pi_j>\pi_i}|, ] the resulting inversion sequence satisfies [ 0\leq e_i\leq i-1 ] and [ \operatorname{inv}(\pi)=\sum_{i=1}^{n}e_i. ] Every sequence satisfying these bounds corresponds to a unique permutation. The product formula for the inversion generating function follows directly because the coordinate (e_i) contributes one of the powers [ 1,q,\ldots,q^{i-1}. ]
A closely related encoding is the Lehmer code, [ c_i=|{j>i:\pi_j<\pi_i}|, ] whose coordinates satisfy (0\leq c_i\leq n-i). Its digit sum is again the inversion number, while its factorially weighted sum gives the lexicographic rank of the permutation. Inversion sequences and Lehmer codes count the same inverted pairs from opposite endpoints.
Sorting and comparison complexity
An adjacent exchange that places an inverted neighboring pair into increasing order removes exactly one inversion and creates none elsewhere. Consequently, any sorting method restricted to adjacent transpositions performs at least (\operatorname{inv}(\pi)) exchanges on input (\pi). Bubble sort, when formulated through adjacent exchanges of inverted pairs, performs exactly that many exchanges, although its number of comparisons need not equal the inversion number.
Inversion counting does not require explicitly carrying out every adjacent exchange. A merge sort-based computation counts cross-inversions while merging sorted subsequences and has time complexity (O(n\log n)). Equivalent asymptotic bounds arise from a Fenwick tree or another data structure supporting prefix-frequency queries. The distinction between counting inversions and physically resolving them explains why a permutation can have (\Theta(n^2)) inversions while its inversion number remains computable in (O(n\log n)) time.
Rank distance
For two rankings represented by permutations (\sigma) and (\pi), their relative permutation can be formed as (\sigma^{-1}\pi), subject to the selected composition convention. The inversion number of this relative permutation counts pairs ordered differently by the two rankings. This quantity is the Kendall tau distance.
Maurice Kendall developed the associated rank-correlation framework by normalizing concordant and discordant pair counts. When there are no tied ranks, the distance and correlation determine one another because every pair is either concordant or discordant. Extensions involving ties require modified denominators and no longer reduce solely to the inversion number of a permutation.
Generalizations
For a finite Coxeter group, positive roots sent to negative roots by an element form its inversion set. The cardinality of this set equals the element’s Coxeter length, generalizing the correspondence between ordinary inversions and adjacent-transposition length in (S_n).
Inversions can also be defined for words containing repeated symbols by counting index pairs whose values occur in decreasing order. Equal values do not form inversions under the strict convention. The resulting generating functions are (q)-analogues of multinomial coefficients, reflecting the distribution of inversions among multiset permutations.