本文作为对于概率论的复习, 采用概率论的符号体系说明思考过程.
形式化的题面描述
设
为一组互不相同的整数。令 表示所有
个排列构成的样本空间,每个排列
的概率均为
定义随机变量 表示排列
的“陡峭程度”,即
使用期望的线性性化简
由线性期望的性质, 有
注意到对于任意 , 由于排列是均匀随机的, 位置
与
上出现的两个元素具有完全对称性, 因此它们的期望相同. 我们可以设
则有
考虑排列中前两个位置上的数. 对于任意两个不同的数 和
(设
), 排列中出现有序对
或
的情况均可贡献
.
- 统计相邻数的所有可能情况:
- 总情况数:任取两个不同的元素, 共有
种有序选择.
- 对于任意一对不同的数
(其中
), 它们可以以
或
的顺序出现在相邻位置上, 故“相邻种数”为 2.
- 总情况数:任取两个不同的元素, 共有
- 因此, 对于任意一对不同数, 其出现在相邻位置的概率为
进而有
由于对于 满足
, 将无序对
分别考虑两次, 可以写为
对于形如这样求和的处理, 可以很常见地固定一个值取得另一个值. 详见《具体数学》第二章多重求和一节. 具体的技巧是将数组排序做一个转换:
将集合 排序后记作
在这种排序下, 对于任意 , 有
常用技巧告诉我们
因此, 上式可写为
最后得到答案: 得