MathLabs

第1题

设 pn(k)p_n(k) 为集合 {1,…,n}\{1, \ldots, n\}（n≥1n \ge 1）中恰有 kk 个不动点的排列数。证明 ∑k=0nk⋅pn(k)=n!\sum_{k=0}^{n} k \cdot p_n(k) = n!。（集合 SS 的排列 ff 是从 SS 到自身的一一映射；若 SS 中的元素 ii 满足 f(i)=if(i) = i，则称 i 是 ff 的不动点。）
第 3/4 步：用计数 p_n(k) 改写 E[X]
上一步下一步
通俗地说

这只是随机变量平均值的标准公式,用题目已经给出的计数 pn(k)p_n(k) 写出来而已。

E[X]=∑k=0nk⋅P(X=k)=∑k=0nk⋅pn(k)n!\mathbb{E}[X] = \sum_{k=0}^{n} k \cdot P(X=k) = \sum_{k=0}^{n} k \cdot \frac{p_n(k)}{n!}
详细分析

另一方面,按定义,在这 n!n! 个等可能的排列中恰有 pn(k)p_n(k) 个使 X=kX=k,故 P(X=k)=pn(k)/n!P(X=k) = p_n(k)/n!,于是 XX 的期望为 E[X]=∑k=0nk⋅pn(k)/n!\mathbb{E}[X] = \sum_{k=0}^{n} k \cdot p_n(k)/n!。