用τ(......)表示逆序数假设abcde是12345的一个排列,且a<b,那么τ(abcde)=τ(a-1)+τ[(b-1)-1]+τ(cde),对吗?为什么?
对不起,打错了 τ(abcde)=(a-1)+[(b-1)-1]+τ(cde)τ()就是逆序数
a的逆序:就是看a后面的数有几个比a小的。很显然,比a小的数有a-1个,都在a的后面,因此是a-1。同理:比b小的数有b-1个,其中有一个是a在b的前面了,因此比b小且位于b的后面的数有b-1-1个。综上,T(abcde)=a-1+b-1-1+T(cde)。