Question

逆序数 求2n (2n-2) (2n-4)省略号 2 (2n-1) (2n-3) (2n-5)省略号 1 我想通过变换成

Answer 1

如果变换成顺序求的话,这个太麻烦了,

你只要看每个数后面的比它小的个数有几个,再加起来就可以了.

比如2n后面比它小的数共有2n-1个,因此跟2n构成逆序的就有2n-1个,

先看2n-2,它后面比它小的数共有2n-3个,因此跟2n-2构成逆序的共有2n-3个,

2n-4后面比它小的数共有2n-5个,继续下去,直到2后面比它小的数只有1个,

2n-1后面比它小的数共有n-1个,2n-3后面比它小的数共有n-2个,继续直到3后面比它小的数共有1个,

因此此排列的逆序数是（2n-1)+(2n-3)+...+1+(n-1)+(n-2)+...+2+1=(3n^2-n)/2