類題: Complete permutation
\(S_{N} := N\)次対称群， \(k \in N\) に対して，部分群 \(S_{N}^{k} := \{ \sigma \ \vert \ \sigma(k) = k \}\) をとる． 求めたいのは， \(\vert S_{N} - \cup_{k \in N} S_{N}^{k} \vert = \vert S_{N} \vert - \vert \cup_{k \in N} S_{N}^{k} \vert\)．
第二項は，包除原理で求まる． \(I \subset N\) に対して， \(\vert \cap_{k \in I} S_{N}^{k} \vert = (N-\vert I \vert)!\)． また，自然数 \(r\) を固定したとき，\(\vert I \vert = r\) となる \(I\) の取り方は \({}_{N} C_{r}\) 通り．
今回:
\(A\) の取り方を固定して考える．\(A\) の取り方は \({}_{M} P_{N}\) 通り．
\(\mathbb{B} := \) \(M\) 個の異なる数から 異なる\(N\)個を選び，並べた順列全体 とする． \(\vert \mathbb{B} \vert = {}_M P_{N}\) となる． \(\mathbb{B}^{k} := \{ B \in \mathbb{B} \ \vert \ B(k) = k \}\) とおく．
本問の答えは， \(\vert \mathbb{B} - \cup_{k \in N} \mathbb{B}^{k} \vert = \vert \mathbb{B} \vert - \vert \cup_{k \in N} \mathbb{B}^{k} \vert\)． を求めれば十分． これも包除原理で求まる．
\(I \subset N\) をとり，\(r := \vert I \vert \)とおく． \(I\) の取り方は \({}_{N}C_{r}\) 通り． また \(\vert \cap_{k \in I} \mathbb{B}^{k} \vert\) は \(r\) 個は \(B\) の値が決まっていて， 残りの \(M-r\) 個の元から，残りの場所 \(N-r\) 個を決めるから， \({}_{M-r} P_{N-r}\) 通り．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
