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: この和を不動点の組を数えるものとして読む
前のステップ次のステップ
ざっくり言うと

順列を不動点の個数でグループ分けする代わりに、存在する(順列, 不動点)の組を一つずつ数えればよい——総数は同じで、見方が違うだけである。

∑k=0nk⋅pn(k)=#{(f,i):f is a permutation of {1,…,n}, f(i)=i}\sum_{k=0}^{n} k \cdot p_n(k) = \#\{(f,i) : f \text{ is a permutation of } \{1,\ldots,n\},\ f(i)=i\}
詳しい解説

ちょうど kk 個の不動点をもつ順列は、項 k⋅pn(k)k \cdot p_n(k) にちょうど kk(不動点一つにつき一つ)だけ寄与する。kk について和をとると、∑k=0nk⋅pn(k)\sum_{k=0}^{n} k \cdot p_n(k) は、ff が {1,…,n}\{1,\ldots,n\} の順列であり ii が ff の不動点である(すなわち f(i)=if(i)=i である)すべての組 (f,i)(f,i) を数えていることになる。