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 步：固定元素成为不动点的概率
上一步下一步
通俗地说

在全部 n!n! 种打乱方式中,恰好把 ii 送回自身的比例正是 1/n1/n——由对称性,这 nn 个元素中的每一个成为 ii 的像的可能性都相同。

P(f(i)=i)=(n−1)!n!=1n,i=1,…,nP(f(i)=i) = \frac{(n-1)!}{n!} = \frac{1}{n}, \qquad i=1,\ldots,n
详细分析

从 {1,…,n}\{1,\ldots,n\} 的 n!n! 个排列中均匀随机取一个 ff。对固定的 ii,n!n! 个排列中恰有 (n−1)!(n-1)! 个满足 f(i)=if(i)=i(与之前相同的计数方式),因此 P(f(i)=i)=(n−1)!/n!=1/nP(f(i)=i) = (n-1)!/n! = 1/n。