求排列的逆序数 n（n-1）...21,答案是n（n-1）/2,为什么要用到等差求和公式或者别的什么方法做?
问题描述：
求排列的逆序数 n（n-1）...21,答案是n（n-1）/2,为什么要用到等差求和公式或者别的什么方法做?
答
计算逆序数的方法:
从左至右,计每个数的右边比它小的数的个数,求和即为排列的逆序数.
逆序数 n（n-1）...21
= (n-1) + (n-2) + ...+ 1 + 0
= n(n-1)/2.为什么不是从n开始加，要从 (n-1)开始加(n-2)n 的右边 比n小的数 有 (n-1) 个, 与n构成n-1个逆序