在学习数据结构的时候看到了以下定理：
但是老师并没有解释，本着钻研的精神决定搞清楚为什么是这个数。
在百度 google一番之后并没有找到，决定自己试着证明。
最开始走了一些弯路，但突然灵光一闪很容易的证明了，所以特此记录
在逆序对中有一个定理，那就是如果两个排列刚好倒序那么他们的逆序数对之和为一个常数
如 {1,2,3,4} 与 {4,3,2,1} 的逆序对前者为0 ,后者为6,和为6.
又如 {2,3,1,4} 与 {4,1,3,2} 的逆序对前者为2 后者为 4 ，和为6.
他们的和全都满足上述公式。
这一点很好证明：
- 在一个任意N个不同数的序列中，第i(1<i<n)大的数一共有n-i个数比它大。
例：{1,2,3,4}中 比2大的数字有{3,4} 两个（4-2）
- 在一个任意N个不同数的互为反序的两个排列中，设前者序列中第i大数的逆序数为a（意思就是在这个数前面有a个数比它大）
那么在此序列中这个数的后面有n-i-a个数比它大（总的比它大的数= 这个数前面比它大的数+后面比它大的数的个数）。
所以将次序列反向后这个数的逆序对为n-i-a。所以两个序列逆序对之和为：
有了以上两个证明，题设的结论就很容易得出了.
因为在一个任意N个不同数可以组成n的全排列个数n！个数，
互为反序的对数为
所以总个数为
平均数为
证毕！
参考文献