Question

两道 线性代数 求逆序数题

Answer 1

第一题结果是n(n-1)/2
首先，前n个数都是从小到大排列的，没有逆序数对。
然后，看2，前面n个数除了1以外的n-1个数都比它大，每一个都与它组成一对逆序数对，就有n-1个；
接着，看4，前面n个数除了1和3以外的n-2个数都比它大，每一个都与它组成一对逆序数对，就有n-2个；
。。。。。
到了2n-2时，就只有2n-1比它大，有一个逆序数对。
2n
是0.
加起来就是
0+1+2+……（n-1）=n(n-1)/2
第二题结果是n(n-1)
首先，前n个数都是从小到大排列的，没有逆序数对。
然后，看2，前面2n-1个数除了1以外的2n-2个数都比它大，每一个都与它组成一对逆序数对，就有2n-2个；
接着，看4，前面2n-2个数除了1和3以外的2n-4个数都比它大，每一个都与它组成一对逆序数对，就有2n-4个；
。。。。。
到了2n-2时，有2个比它大，有2个逆序数对。
2n
是0.
加起来就是
2*【0+1+2+……（n-1）】=n(n-1)