任意N个不同数的逆序对平均值

在学习数据结构的时候看到了以下定理:
任意N个不同数的逆序对平均值

但是老师并没有解释,本着钻研的精神决定搞清楚为什么是这个数。

在百度 google一番之后并没有找到,决定自己试着证明。
最开始走了一些弯路,但突然灵光一闪很容易的证明了,所以特此记录

在逆序对中有一个定理,那就是如果两个排列刚好倒序那么他们的逆序数对之和为一个常数

$\frac{n(n-1))}{2}$

如 {1,2,3,4} 与 {4,3,2,1} 的逆序对前者为0 ,后者为6,和为6.

又如 {2,3,1,4} 与 {4,1,3,2} 的逆序对前者为2 后者为 4 ,和为6.

他们的和全都满足上述公式。
这一点很好证明:

  1. 在一个任意N个不同数的序列中,第i(1<i<n)大的数一共有n-i个数比它大。
    例:{1,2,3,4}中 比2大的数字有{3,4} 两个(4-2)

  2. 在一个任意N个不同数的互为反序的两个排列中,设前者序列中第i大数的逆序数为a(意思就是在这个数前面有a个数比它大)
    那么在此序列中这个数的后面有n-i-a个数比它大(总的比它大的数= 这个数前面比它大的数+后面比它大的数的个数)。
    所以将次序列反向后这个数的逆序对为n-i-a。所以两个序列逆序对之和为:

$\sum_{1}^{n}[a+(n-i-a)]
\\=\sum_{1}^{n}(n-i)
\\=\frac{n(n-1))}{2}$

有了以上两个证明,题设的结论就很容易得出了.

因为在一个任意N个不同数可以组成n的全排列个数n!个数,
互为反序的对数为

$\frac{n!}{2}$

所以总个数为

$M = \frac{n!}{2}\times \frac{n(n-1))}{2}$

平均数为

$\frac{M}{n!}=\frac{n(n-1)}{4}$

证毕!

参考文献

百度百科.逆序数. http://baike.baidu.com/

上一篇:MySQL5.1升级5.6后,执行grant出错:ERROR 2013 (HY000): Lost connection to MySQL server during query【转载】


下一篇:Sticker.js – 帮助你在网站中加入贴纸效果