求下列排列的逆序数1 3…(2n-1)2 4…(2n)看不懂啊 啥省略号啥的 也不是通项吧

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

manager1 幼苗

共回答了14个问题采纳率:92.9% 举报

逆序数等于对每个数之后比它小的数的个数求和,也等于对每个数之前比它大的数的个数求和.
我们选择对每个数之后比它小的数的个数求和.该排列是将顺序排列中所有奇数抽出顺序放在最前,偶数顺序留在放在最后构成的.由于偶数顺序,且在最后,偶数不会与其后的数构成逆序对.奇数虽然顺序,但后面还有偶数,随意奇数会与比它小的偶数构成逆序对.所以有
Σ((i-1)/2) (i=1,3,5,.,2n-1) (i-1)/2,显然是比奇数i小的正偶数个数,所以利用简单的等差数列求和,可知逆序数为n*(n-1)/2

1年前

10
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.294 s. - webmaster@yulucn.com