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 の不動点という。）
ステップ 4/4: E[X] の二つの式を組み合わせる
前のステップ次のステップ
ざっくり言うと

どちらの道筋も同じ平均値を計算しているので、それらを等しいとおけば、これ以上の計算なしに証明が完成する。

∑k=0nk⋅pn(k)=n!⋅E[X]=n!\sum_{k=0}^{n} k \cdot p_n(k) = n! \cdot \mathbb{E}[X] = n!
詳しい解説

ステップ2とステップ3で得た E[X]\mathbb{E}[X] の二つの式を等しいとおくと、∑k=0nk⋅pn(k)/n!=1\sum_{k=0}^n k\cdot p_n(k)/n! = 1、すなわち ∑k=0nk⋅pn(k)=n!\sum_{k=0}^n k\cdot p_n(k) = n! が得られ、これはまさに証明すべき等式である。