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 を満たすとき、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 である。