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: 二つの数え方を一致させて結論を得る
前のステップ次のステップ
ざっくり言うと

同じ集まりを正しく数える二つの方法は同じ数を与えなければならない——それが証明のすべてである。

∑k=0nk⋅pn(k)=n⋅(n−1)!=n!\sum_{k=0}^{n} k \cdot p_n(k) = n \cdot (n-1)! = n!
詳しい解説

ステップ1とステップ3は、まったく同じ組 (f,i)(f,i) の集合を二通りの方法で数えているので、二つの式は等しくなければならない:∑k=0nk⋅pn(k)=n⋅(n−1)!=n!\sum_{k=0}^{n} k\cdot p_n(k) = n\cdot(n-1)! = n!、これが求めるものである。