讨论排列n(n-1)...21的逆序数，并讨论排列的奇偶性

Question

如题所述

Answer 1

任意选出两个，都满足：前>后，构成一对逆序数。

逆序数=c(n，2)=n(n-1)/2

当n和n-1中有一个是4的倍数时，为偶序列；当n和n-1中没有4的倍数时，为奇排列。

对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的实际先后次序与标准次序不同时，就说有1个逆序。

扩展资料：

计算一个排列的逆序数的直接方法是逐个枚举逆序，同时统计个数。例如在序列 { 2, 4, 3, 1 } 中，逆序依次为 (2，1)，(4，3)，(4，1)，(3，1)，因此该序列的逆序数为 4。

虽然简单直观，但是其时间复杂度是 O(n^2)。一个更快（但稍复杂）的计算方法是在归并排序的同时计算逆序数。

Answer 2

大一数学作业，问同学吗，参考一下。t=（n-21+1）*（n-21）/2=（n-21）（n-20）/2，那个符号打不岀来啊，奇偶性有点麻烦啊，n>=22，n=22+4k或22+k时为奇排列，n为22+2k或22+3k时为偶排列。

Answer 3

任意选出两个，都满足：前>后，构成一对逆序数。
逆序数=c(n,2)=n(n-1)/2
n=4k，
2k(4k-1)
偶
n=4k+1，
2k(4k+1)
偶
n=4k+2，(2k+1)(4k+1)
奇
n=4k+3，(2k+1)(4k+3)
奇