逆序对

逆序

设为一个排列，如果而且，
这个序位或这一对元素被称为是的一个逆序。通常逆序是对于排列的定义，但也可以用于序列：
设是一个序列（或多重排列）。如果而且，
这个序位或这对元素被称为是的一个逆序。
对于根据元素组成的序列，逆序的定义不是唯一的，因为不同的序位上可能有相同的值对。逆序集是所有逆序的集合。一个排列依其序位而定义的逆序集是，它的反向排列依其序位而定义的逆序集，反之亦然，只是交换了配对的元素。

逆序数

逆序数是逆序集的基数，它常用于量度排列或序列的已排序程度。
在一个排列的箭头指向图中，它是箭头指向相交叉的数，也是从自指(identity)排列而得到的Kendall tau距离，以及每个反向相关向量的和，如下列定义。
对于逆序数，依序位或依元素而定义的分别并不重要，因为排列及其反向排列都具有相同的逆序数。
其它测量（预先）排序程度的方式，包括了为排好序列而从序列中可以删除元素的最小数量，对序列所“进行”排序的次数和长度，每个元素在已排序位置之上的距离总和（Spearman footrule），以及排序过程中必需的最少交换次数。比较排序算法计算逆序数的时间为O(n log n)。

排列的弱次序

n物品排列的集合其部分次序的结构，称为排列的弱次序，而构成格。
以逆序集的子集关系绘出的哈斯图，则构成了称为permutohedron的骨架。
如果依位置将某一排列分配给每个逆序集，所得到的排序是permutohedron的次序，其中的边对应于连续两元素的交换。这是排列的弱排序。The identity is its minimum, and the permutation formed by reversing the identity is its maximum.
如果依元素将某一排列分配给每个逆序集，所得到的排序将是凯莱图的次序，其中的边对应于连续两元素的交换。对称组的凯莱图与其permutohedron相似，但是每个排列由其反向替换。