求1 3...(2n-1)(2n)(2n-2)...2的逆序数
问题描述:
求1 3...(2n-1)(2n)(2n-2)...2的逆序数
答
1 3...(2n-1)(2n)(2n-2)...2
考虑前一半1 3...(2n-1)没有逆序
后一半(2n)(2n-2)...2是完全倒叙的,逆序数为C(2,n)
前一半的每一个和后一半的每一个组合都是一个逆序,个数是C(2,n)
所以逆序数为2*C(2,n)=2*(n-1)*n/2=n*(n-1)