线性代数问题 已知n阶全排列p1p2…pn的逆序数为k,求n阶全排列pnpn-1…p1的逆序数,

Question

如题所述

Answer 1

线性代数问题 已知n阶全排列p1p2…pn的逆序数为k,求n阶全排列pnpn-1…p1的逆序数为：
n(n-1)/2-k
【简单的验证了下：若全顺排，逆序数为零；全逆排，逆序数为n(n-1)/2。另外用特例验证了一下（五位，六位）。】

Answer 2

逆序数是：0.5*n*(n-1)-k
0.5*n*(n-1)是奇数则要讨论的为奇
若0.5*n*(n-1)为偶数则要讨论的为偶数.
其实从第一个逆序换到第二个共换了0.5*n*(n-1)次,且奇数次互换是要改变奇偶性的.
至于第一问就是这样的
把一个逆序完全倒换过来则二者逆序数之和为0.5*n*(n-1).
叙述的不够清楚多多包涵追问

看不懂这个

本回答被提问者采纳

Answer 3

如果把原序列倒过来的话，它的逆序数是 n*(n-1)/2 - K
原因在于 上述的这两个的逆序数之和为 1+2+3+4+.......+(n-1)=n*(n-1)/2
你可以随便举几个例子验算下。本回答被网友采纳

Answer 4

Answer 5

p1，p2，…，pn 的逆序数最大值是 (1/2)n(n-1),

pn，..., p2, p1 的逆序数是 (1/2)n(n-1) - k