排列135...(2n-1)246...(2n)的逆序数是什么?

2020-08-30 社会 424阅读

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

声明:你问我答网所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系fangmu6661024@163.com