Question

求排列n(n-1)....3,2,1的逆序数，并讨论该排列的奇偶性 ？

Answer 1

逆序数是n(n-1)/2。

假设n是偶数，则n＝2m，m是奇数或偶数，所以n(n-1)/2=m(2m-1)。这里的2m-1肯定是奇数，但是m可奇可偶，所以当m是奇数2k+1（此时n＝2m=4k+2）时，n(n-1)/2是奇数。当m是偶数2k（此时n＝2m=4k）时，n(n-1)/2是偶数。

假设n是奇数，则n＝2m+1，m是奇数或偶数，所以n(n-1)/2=m(2m+1)。同样的讨论，得到结论：当m是奇数2k+1（此时n＝2m+1=4k+3）时，n(n-1)/2是奇数。当m是偶数2k（此时n＝2m+1=4k+1）时，n(n-1)/2是偶数。

综上，当n=4k或4k+1是偶排列，当n=4k+2或4k+3时，是奇排列。

Answer 2

第一个n
的逆序数是0
第二个n-1的逆序数是1
第三个n-2的逆序数是2
.....................................
第n个1
的逆序数是
n-1
∴逆序数是0+1+2+3+........n-1
(n-1+0)*n/2
=n(n-1)/2
因为n(n-1)是连续的两个自然数。
∴当n或(n-1)是4的倍数时，是偶排列
当n或(n-1)是只能是2的倍数时,是奇排列