逆序数
在一个排列（也就是数列）中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为该排列的逆序数。逆序数为奇数的排列称为奇排列，逆序数为偶数的排列称为偶排列。
比如有这么一个排列：
为了计算它的逆序数，先单独算出每个数字的。比如该排列的第三个数字5之前，没有一个数字大于它，也就是没有一个逆序的，那么记作
再比如，第四个4之前，有一个逆序的，记作
数列内每个数字都可以求出对应的
然后将所有数字的
因为算出来逆序数为6，所以这是偶排列。
一个排列中任意的两个元素对换，排列改变奇偶性。
不妨假设元素为从1开始的自然数（从小到大为标准次序）。
先证相邻对换的情形。
设排列：
很显然，这些元素的逆序数不会改变：
而
-
：对换后， 的逆序数+1， 的逆序数不变 -
：对换后， 的逆序数不变， 的逆序数-1
总之，对换前后，奇偶性改变。
再证一般对换的情形。
设排列为：
首先：
再：
总共
比如排列：
和之前比，5和2对换了，各个数字的
所以变成了奇排列：
关注马同学
微信公众号：matongxue314
