Question

设排列a1a2⋯an的逆序数为t,试求排列anan－1⋯a2a1的逆序数

Answer 1

（a1 a2 ...an的逆序数）+（an...a2 a1的逆序数）=定值

将这个排列从小到大的顺序排列,则逆序数为0；

再将排列反过来,得到由大到小的递减排列,

其逆序数为（n-1）+(n-2)+...+2+1=(n-1)n/2,

这个定值就是（n-1）n/2

那么所求结果就是 （n-1）n/2-t