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 的不动点。）
第 2/4 步：由期望的线性性得 E[X] = 1
上一步下一步
通俗地说

即使各事件并不独立,期望的线性性也允许我们把每个元素被固定的各自概率直接相加。

X=∑i=1n1{f(i)=i},E[X]=∑i=1nP(f(i)=i)=n⋅1n=1X = \sum_{i=1}^{n} \mathbf{1}_{\{f(i)=i\}}, \qquad \mathbb{E}[X] = \sum_{i=1}^{n} P(f(i)=i) = n \cdot \frac{1}{n} = 1
详细分析

设 XX 为 ff 的(随机)不动点个数,即指示变量之和 X=∑i=1n1{f(i)=i}X = \sum_{i=1}^n \mathbf{1}_{\{f(i)=i\}}。无论指示变量之间是否相关,期望的线性性都成立,所以 E[X]=∑i=1nP(f(i)=i)=n⋅1n=1\mathbb{E}[X] = \sum_{i=1}^{n} P(f(i)=i) = n\cdot\frac{1}{n} = 1。