Question

按自然数从小到大为标准次序，求各排列的逆序数：（1）1 3···（2n-1）2 4···（2n）；

（2）1 3···（2n-1）（2n）（2n-2）····2

Answer 1

排列（1）的逆排列是：2n,...,4,2,2n-1,...,3,1
对于偶数2k，逆序数是n-k+1，对于奇数2k-1,逆序数是2n-k+1
另：逆排列中第i个数的值是：当i<=n,是偶数2（n-i+1），
当i>n是奇数2（i-1）-1
排列（2）的逆排列是：2,...,2n-2，2n,2n-1,...,3,1
对于偶数2k，逆序数是k，对于奇数2k-1,逆序数是2n-k+1
另：逆排列中第i个数的值是：当i<=n,是偶数2i，
当i>n是奇数2（i-1）-1

Answer 2

因为奇数和偶数分别是从小到大排列的，所以一个奇数和一个偶数才能组成一个逆序对，
含3的有1对，含5的有2对，……，含2n-1的有n-1对，
所以逆序数=1+2+3+……+(n-1)=
n(n-1)/2