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: 選んだ一つの元を固定する順列を数える
前のステップ次のステップ
ざっくり言うと

ii の行き先——すなわち自分自身——を固定してしまえば、順列の残りの部分は他の n−1n-1 個の元に対して自由に何でもできる。

#{f:f(i)=i}=(n−1)!for each fixed i∈{1,…,n}\#\{f : f(i)=i\} = (n-1)! \quad \text{for each fixed } i \in \{1,\ldots,n\}
詳しい解説

元 i∈{1,…,n}i \in \{1,\ldots,n\} を一つ固定する。f(i)=if(i)=i を満たす順列 ff は、残りの n−1n-1 個の元 {1,…,n}∖{i}\{1,\ldots,n\}\setminus\{i\} をどのように並べ替えるかによって完全に決まり、そのような並べ替えはすべて許される。したがって、ii を固定する {1,…,n}\{1,\ldots,n\} の順列はちょうど (n−1)!(n-1)! 個存在する。