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 步：对 i 的全部 n 种取法求和
上一步下一步
通俗地说

可以被固定的元素共有 nn 个,每个都贡献相同的计数 (n−1)!(n-1)!,因此直接相乘即可。

#{(f,i):f(i)=i}=∑i=1n(n−1)!=n⋅(n−1)!\#\{(f,i): f(i)=i\} = \sum_{i=1}^{n} (n-1)! = n \cdot (n-1)!
详细分析

把上一步的计数对 i∈{1,…,n}i \in \{1,\ldots,n\} 的所有取法求和,就得到满足 f(i)=if(i)=i 的对 (f,i)(f,i) 的总数:∑i=1n(n−1)!=n⋅(n−1)!\sum_{i=1}^{n}(n-1)! = n\cdot(n-1)!。