第N个数和前面的数产生的互逆数的分布是0到N-1的均匀分布,所以有
这显然是个卷积运算,直接用生成函数得到结论:
又有
所以
将这个多项式乘开,对应的 前面的系数就是 即逆序数为k的概率。
根据等比数列求和公式也可以写为
具体的系数有没有简单的表达式就不知道了