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 步：对照两种计数方式得出结论
上一步下一步
通俗地说

对同一集合的两种如实计数必须得到同一个数——这就是整个证明。

∑k=0nk⋅pn(k)=n⋅(n−1)!=n!\sum_{k=0}^{n} k \cdot p_n(k) = n \cdot (n-1)! = n!
详细分析

第1步与第3步以两种不同方式统计了完全相同的一组对 (f,i)(f,i),因此两个表达式必然相等:∑k=0nk⋅pn(k)=n⋅(n−1)!=n!\sum_{k=0}^{n} k\cdot p_n(k) = n\cdot(n-1)! = n!,这正是所要证明的。