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 的不动点。）
第 4/4 步：结合 E[X] 的两个表达式
上一步下一步
通俗地说

两条路径计算的是同一个平均值,令二者相等即可完成证明,无需再做任何计算。

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

令第2步与第3步得到的 E[X]\mathbb{E}[X] 的两个表达式相等,得 ∑k=0nk⋅pn(k)/n!=1\sum_{k=0}^n k\cdot p_n(k)/n! = 1,即 ∑k=0nk⋅pn(k)=n!\sum_{k=0}^n k\cdot p_n(k) = n!,这正是所要证明的等式。