已知X1X2……Xn的逆序数是M,求Xn……X2X1的逆序数?答案是n(n-1)/2-M,请详细说明得出结论的步骤
问题描述：
已知X1X2……Xn的逆序数是M,求Xn……X2X1的逆序数?
答案是n(n-1)/2-M,请详细说明得出结论的步骤
答
序列1,2,3,...,n中有有序对C(n,2)=n(n-1)/2对：
(1,2),(1,3),...,(1,n),(2,3),...,(2,n),...,(n-1,n).
记a1=x1,a2=x2,...,an=xn,b1=xn,...,bn=x1.
对于有序对(i,j),若(ai,aj)是a1a2...an逆序,那么(bi,bj)是b1b2...bn的顺序,反之亦然,所以a1a2...an的逆序数加b1b2...bn的逆序数等于n(n-1)/2,Xn……X2X1的逆序数等于n(n-1)/2-M.