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 的不动点。）
第 1/4 步：把该和理解为对不动点对的计数
上一步下一步
通俗地说

与其按不动点个数把排列分组,不如逐一数出所有存在的(排列, 不动点)对——总数是一样的,只是换了个角度看。

∑k=0nk⋅pn(k)=#{(f,i):f is a permutation of {1,…,n}, f(i)=i}\sum_{k=0}^{n} k \cdot p_n(k) = \#\{(f,i) : f \text{ is a permutation of } \{1,\ldots,n\},\ f(i)=i\}
详细分析

恰有 kk 个不动点的排列恰好为项 k⋅pn(k)k \cdot p_n(k) 贡献 kk(每个不动点贡献一次)。对 kk 求和后,∑k=0nk⋅pn(k)\sum_{k=0}^{n} k \cdot p_n(k) 统计的正是所有满足 ff 是 {1,…,n}\{1,\ldots,n\} 的排列且 ii 是 ff 的不动点(即 f(i)=if(i)=i)的对 (f,i)(f,i)。