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 の不動点という。）
ステップ 3/4: i のすべての n 通りの選び方について数を合計する
前のステップ次のステップ
ざっくり言うと

固定できる元は nn 個あり、それぞれが同じ数 (n−1)!(n-1)! を寄与するので、単純に掛け合わせればよい。

#{(f,i):f(i)=i}=∑i=1n(n−1)!=n⋅(n−1)!\#\{(f,i): f(i)=i\} = \sum_{i=1}^{n} (n-1)! = n \cdot (n-1)!
詳しい解説

前のステップの数を i∈{1,…,n}i \in \{1,\ldots,n\} のすべての選び方について合計すると、f(i)=if(i)=i を満たす組 (f,i)(f,i) の総数が得られる:∑i=1n(n−1)!=n⋅(n−1)!\sum_{i=1}^{n}(n-1)! = n\cdot(n-1)!。