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 の不動点という。）
ステップ 2/4: 期待値の線形性により E[X] = 1
前のステップ次のステップ
ざっくり言うと

期待値の線形性により、事象同士が独立でなくても、各元が不動点となる個々の確率を足し合わせることができる。

X=∑i=1n1{f(i)=i},E[X]=∑i=1nP(f(i)=i)=n⋅1n=1X = \sum_{i=1}^{n} \mathbf{1}_{\{f(i)=i\}}, \qquad \mathbb{E}[X] = \sum_{i=1}^{n} P(f(i)=i) = n \cdot \frac{1}{n} = 1
詳しい解説

XX を ff の(確率変数としての)不動点の個数、すなわち指示変数の和 X=∑i=1n1{f(i)=i}X = \sum_{i=1}^n \mathbf{1}_{\{f(i)=i\}} とする。期待値の線形性は指示変数間の依存関係にかかわらず成り立つので、E[X]=∑i=1nP(f(i)=i)=n⋅1n=1\mathbb{E}[X] = \sum_{i=1}^{n} P(f(i)=i) = n\cdot\frac{1}{n} = 1 である。