大门|大门-CS-2003 |问题61

在排列a1中…。。一个n个不同的整数，一个反转是一对（ai，aj），这样i aj。如果所有排列的可能性相等，那么在随机选择的1….排列中，预期的反转数是多少…。。N （A） n（n-1）/2

（B） n（n-1）/4 （C） n（n+1）/4 （D） 2n[log2n] 答复: （B） 说明：

There are n(n-1)/2 pairs such that i < j.

For a pair (ai, aj), probability of being inversion is 1/2.

Therefore expected value of inversions = 1/2 * (n(n-1)/2)
                                       = n(n-1)/4

这个问题的小测验