n个数排列为i1,i2.in.逆序数是k,那么排列in,in-1,...,i2,i1,的逆序是多少?请说理由!
来源:学生作业帮助网 编辑:作业帮 时间:2024/08/01 06:16:07
![n个数排列为i1,i2.in.逆序数是k,那么排列in,in-1,...,i2,i1,的逆序是多少?请说理由!](/uploads/image/z/3238642-10-2.jpg?t=n%E4%B8%AA%E6%95%B0%E6%8E%92%E5%88%97%E4%B8%BAi1%2Ci2.in.%E9%80%86%E5%BA%8F%E6%95%B0%E6%98%AFk%2C%E9%82%A3%E4%B9%88%E6%8E%92%E5%88%97in%2Cin-1%2C...%2Ci2%2Ci1%2C%E7%9A%84%E9%80%86%E5%BA%8F%E6%98%AF%E5%A4%9A%E5%B0%91%3F%E8%AF%B7%E8%AF%B4%E7%90%86%E7%94%B1%21)
xŐJ@_EwI3봾PP`,-mvD(@ߥf+x2O
d|snV?
nП/
M6bP%fu줿FNUkQ
ZdEQ|1wN##rfaߏK&fETp|,kfVb0hW9l21$Ļaʝ
5s`1ÎʉHJMN9E`5-?{vl?EtH "SC%_&'PY_)w;@,(to1 ɁX^Q]7uR4HД6EnQ
n个数排列为i1,i2.in.逆序数是k,那么排列in,in-1,...,i2,i1,的逆序是多少?请说理由!
n个数排列为i1,i2.in.逆序数是k,那么排列in,in-1,...,i2,i1,的逆序是多少?请说理由!
n个数排列为i1,i2.in.逆序数是k,那么排列in,in-1,...,i2,i1,的逆序是多少?请说理由!
n个数间的“序”有(n-1)(n-2)/2个
i1,i2.in.逆序数是k,那么排列in,in-1,...,i2,i1,的逆序是(n-1)(n-2)/2-k
简单说说,不知对不对,n个数逆序数最多为N=(n-1)n/2,所以倒过来的数列逆序数为N-k
后面这个排列的逆序数是n(n-1)/2。
因为n后面比n小的数有n-1个;
n-1后面比n-1小的数有n-2个;
... ...
2后面比2小的数有1个;
1后面比1小的数有0个;
0+1+2+...+(n-1)=n(n-1)/2