66问答网
所有问题
线性代数问题 已知n阶全排列p1p2…pn的逆序数为k,求n阶全排列pnpn-1…p1的逆序数,
如题所述
举报该问题
推荐答案 2017-06-27
线性代数
问题 已知n阶
全排列
p1p2…pn的逆序数为k,求n阶全排列pnpn-1…p1的逆序数为:
n(n-1)/2-k
【简单的验证了下:若全顺排,逆序数为零;全逆排,逆序数为n(n-1)/2。另外用特例验证了一下(五位,六位)。】
温馨提示:答案为网友推荐,仅供参考
当前网址:
http://66.wendadaohang.com/zd/UvDv9vxDx9psix2si2i.html
其他回答
第1个回答 2016-03-15
逆序数是: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).
叙述的不够清楚多多包涵
追问
看不懂这个
本回答被提问者采纳
第2个回答 推荐于2017-06-28
如果把原序列倒过来的话,它的
逆序数
是 n*(n-1)/2 - K
原因在于 上述的这两个的逆序数之和为 1+2+3+4+.......+(n-1)=n*(n-1)/2
你可以随便举几个例子验算下。
本回答被网友采纳
第3个回答 2017-05-18
第4个回答 2017-05-15
p1,p2,…,pn 的逆序数最大值是 (1/2)n(n-1),
pn,..., p2, p1 的逆序数是 (1/2)n(n-1) - k
1
2
下一页
相似回答
大家正在搜
相关问题
r(P1P2…Pn)=k表示什么?
1,2,……,n的全排列共有逆序数是多少,要详细解答
设τ(j1j2…jn)=k,试求τ(jn…j2j1),其中j...
大学线性代数全排列中a1p1 a2p2代表什么 求详解
一道ACM题,求逆序对问题
当排列数中出现相同的数时,逆序数怎么计算,比如145243