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

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