逆序对

設${\displaystyle \pi }$為一個排列，如果${\displaystyle i<j}$而且${\displaystyle \pi (i)>\pi (j)}$， 這個序位${\displaystyle (i,j)}$或這一對元素${\displaystyle {\bigl (}\pi (i),\pi (j){\bigr )}}$被稱為是${\displaystyle \pi }$的一個逆序。通常逆序是對於排列的定義，但也可以用於序列：

設${\displaystyle S}$是一個序列（或多重排列）。如果${\displaystyle i<j}$而且${\displaystyle S(i)>S(j)}$， 這個序位${\displaystyle (i,j)}$或這對元素${\displaystyle {\bigl (}S(i),S(j){\bigr )}}$被稱為是${\displaystyle S}$的一個逆序。

對於根據元素組成的序列，逆序的定義不是唯一的，因為不同的序位上可能有相同的值對。逆序集是所有逆序的集合。一個排列依其序位而定義的逆序集是，它的反向排列依其序位而定義的逆序集，反之亦然，只是交換了配對的元素。

逆序數是逆序集的基數，它常用於量度排列或序列的已排序程度。

在一個排列的箭頭指向圖中，它是箭頭指向相交叉的數，也是從自指(identity)排列而得到的Kendall tau距離，以及每個反向相關向量的和，如下列定義。

對於逆序數，依序位或依元素而定義的分別並不重要，因為排列及其反向排列都具有相同的逆序數。

其它測量（預先）排序程度的方式，包括了為排好序列而從序列中可以刪除元素的最小數量，對序列所“進行”排序的次數和長度，每個元素在已排序位置之上的距離總和（Spearman footrule），以及排序過程中必需的最少交換次數。比較排序算法計算逆序數的時間為O(n log n)。

有三個類似的向量用於將排列的逆序，壓縮到確定唯一的向量中。它們通常被稱為逆序向量或Lehmer碼。本文將逆序向量記為(${\displaystyle v}$)，其它的兩個向量有時分別稱為左和右逆序向量；為了避免與前面的逆序向量混淆，本文將另兩個分別稱為左逆序計數${\displaystyle l}$和右逆序計數${\displaystyle r}$。左逆序計數是以反向colexicographic次序的排列，右逆序計數則是以字典次序的排列。

Rothe diagram

逆序向量${\displaystyle v}$： 依據元素的定義，${\displaystyle v(i)}$是較小（右）分量為${\displaystyle i}$的逆序數。${\displaystyle v(i)}$是在${\displaystyle \pi }$之中的${\displaystyle i}$之前，元素較${\displaystyle i}$大的數量。

${\displaystyle v(i)~~=~~\#\{k\mid k>i~\land ~\pi ^{-1}(k)<\pi ^{-1}(i)\}}$

左逆序計數${\displaystyle l}$： 依據位置的定義，${\displaystyle l(i)}$是較大（右）分量為${\displaystyle l(i)}$的逆序數。${\displaystyle l(i)}$是在${\displaystyle \pi (i)}$之中的${\displaystyle \pi (i)}$之前，元素較${\displaystyle \pi (i)}$大的數量。

${\displaystyle l(i)~~=~~\#\left\{k\mid k<i~\land ~\pi (k)>\pi (i)\right\}}$

右逆序計數${\displaystyle r}$，通常稱為Lehmer碼： 依據位置的定義，${\displaystyle r(i)}$是較小（左）分量為i的逆序數。${\displaystyle r(i)}$是${\displaystyle \pi (i)}$之中的${\displaystyle \pi (i)}$之後，元素較${\displaystyle \pi (i)}$小的數量。

${\displaystyle r(i)~~=~~\#\{k\mid k>i~\land ~\pi (k)<\pi (i)\}}$

Rothe圖可以協助找出${\displaystyle v}$和${\displaystyle r}$。Rothe圖是以黑點來表示1的排列矩陣，每一個位置上若為逆序（通常以叉號表示）則在其右側與下方即有一點。${\displaystyle r(i)}$是圖中第${\displaystyle i}$列排列逆序的加總，而${\displaystyle v(i)}$是${\displaystyle i}$欄中排列逆序的加總。排列矩陣的倒反即是此矩陣的轉置，因此某一排列的${\displaystyle v}$即是它轉置的${\displaystyle r}$，反之亦然。