线性代数 设n阶排列a1a2a3…an的逆序数为s,求排列anan-1…a2a1的逆序数

yjfnm 1年前 已收到1个回答 举报

镇静 幼苗

共回答了21个问题采纳率:100% 举报

对于1到n中任意两个数 i,j,
它们要么在 a1a2a3…an中构成逆序,要么在anan-1…a2a1中构成逆序
两者恰居其一
所以两个排列的逆序数的和为 C(n,2)=n(n-1)/2
所以 anan-1…a2a1 的逆序数为 n(n-1)/2 - s.

1年前 追问

8

yjfnm 举报

为什么两个排列逆序数的和为n(n-1)/2

举报 镇静

上面说了:
对于1到n中任意两个数 i,j,
它们要么在 a1a2a3…an中构成逆序, 要么在anan-1…a2a1中构成逆序
两者恰居其一
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.036 s. - webmaster@yulucn.com