令A [1 .. n]为n个distinct数字的数组。如果i A
[j]，则对（i，j）被称为A的倒置。（有关倒置的更多信息，请参阅问题2-4。）假设选择了A的每个元素从1到n范围内随机，独立且均匀地分布。使用指标随机变量来计算预期的反转次数。

问题来自Cormen的 算法简介中的 练习5.2-5 。这是我的递归解决方案：

假定x（i）是在一个倒[1..i]和E（i）的数目为x（i）的预期值，则E（i + 1的）可以计算如下：
图像我们有i+1放置所有数字的位置，如果我们将 i + 1 放在第一个位置，则x（i + 1）= i + x（i）; 如果我们将 i +
1 放在第二个位置上，则x（i + 1）= i-1 + x（i），…，因此E（i + 1）= 1 /（i + 1） sum（ k）+
E（i），其中k = [0，i]。最后，我们得到E（i + 1）= i / 2 + E（i）。
因为我们知道E（2）= 0.5，所以递归得到：E（n）=（n-1 + n-2 + … + 2）/ 2 + 0.5 = n （n-1）/ 4 。

尽管上面的推论似乎是正确的，但是我仍然不太确定。所以我在这里分享。

如果有什么问题，请纠正我。