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 步：计数固定某一元素的排列个数
上一步下一步
通俗地说

只要固定 ii 的去向——也就是它自己——排列的其余部分就可以对另外 n−1n-1 个元素为所欲为。

#{f:f(i)=i}=(n−1)!for each fixed i∈{1,…,n}\#\{f : f(i)=i\} = (n-1)! \quad \text{for each fixed } i \in \{1,\ldots,n\}
详细分析

固定一个元素 i∈{1,…,n}i \in \{1,\ldots,n\}。满足 f(i)=if(i)=i 的排列 ff 完全由它如何在剩下的 n−1n-1 个元素 {1,…,n}∖{i}\{1,\ldots,n\}\setminus\{i\} 之间重新排列所决定,而这样的每一种排列都是允许的。因此恰好有 (n−1)!(n-1)! 个 {1,…,n}\{1,\ldots,n\} 的排列固定 ii。