完全順列(その3・一般化)

前回前々回は「5人のプレゼント交換会」を行いました.

「\(n\)人のプレゼント交換会」ならどうでしょうか?この場合の完全順列の総数を求めてみましょう.

以下,\(i\)は自然数とします.

完全順列とは,「\(i\)番目に\(i\)が来ないような並び方\((1\leq i \leq n)\)」,すなわち\[\text{\(1\)以上\(n\)以下のすべての\(i\)に対して,\(i\)番目に\(i\)が来ない}\quad\cdots(\ast)\]という意味でした.この総数を求めたい,というわけですね.

今まで見てきた通り,これが一筋縄ではいかない問題でした.まして今回は\(n\)人です.そこで,お馴染みのアイデア:直接求めるのが難しいのなら,全体からその否定を除けばいい,という「余事象」の考え方で攻めてみることにしましょう.というわけで,\((\ast)\)の否定を考えてみます.

「すべての」の否定は「存在する」でしたから(なぜ?),\((\ast)\)の否定は次のようになります.\[\text{\(i\)番目が\(i\)になる\(1\)以上\(n\)以下の\(i\)が存在する}\quad\cdots(\ast\ast)\]

この総数を数え,そして並べ替えの総数\(n!\)から引いてやりましょう.ここで,\(i\)番目が\(i\)となるような事象を\(A_i~(1\leq i \leq n)\)とおくことにします.すると\((\ast\ast)\)となる総数は
\[n(A_1\cup A_2\cup A_3 \cup \cdots \cup A_n)=n \left( \bigcup^n_{i=1}A_i \right)\]と表せることになります.したがって,求める完全順列の総数は
\[n!-n\left(\bigcup^n_{i=1}A_i\right)\]
となります.さて,この式の二項目\(n(\bigcup^n_{i=1}A_i)\)ですが,これは以下のように計算できます(なぜ?).

\[
n\left(\displaystyle\bigcup_{i}^{n} A_i\right)=\displaystyle\sum_{i}^{n} n(A_i)-\displaystyle\sum_{i<j}^{n}n(A_i \cap A_j)+\displaystyle\sum_{i<j<k}^{n}n(A_i \cap A_j \cap A_k)-\cdots+(-1)^{n-1}\displaystyle\sum^{n}_{i<j<\cdots} n(A_i \cap A_j \cap \cdots )
\]

ここで,\[\displaystyle\sum_{i}^{n} n(A_i),~\sum_{i<j}^{n}n(A_i \cap A_j),~\sum_{i<j<k}^{n}n(A_i \cap A_j \cap A_k),\cdots,\sum^{n}_{i<j<\cdots} n(A_i \cap A_j \cap \cdots)\]を求めてみると,
\[
\begin{align*}
&\displaystyle\sum_{i}^{n} n(A_i)={ }_n\mathrm{C}_1\times (n-1)!\\
&\sum_{i<j}^{n}n(A_i \cap A_j)={ }_n\mathrm{C}_2\times(n-2)!\\
&\sum_{i<j<k}^{n}n(A_i \cap A_j \cap A_k)={ }_n\mathrm{C}_3\times(n-3)!\\
&\qquad\qquad\vdots\\
&\sum^{n}_{i<j<\cdots} n(A_i \cap A_j \cap \cdots)={ }_n\mathrm{C}_n\times(n-n)!
\end{align*}
\]
ですから結局,
\[n\left(\displaystyle\bigcup_{i}^{n} A_i\right)={ }_n\mathrm{C}_1\times (n-1)!-{ }_n\mathrm{C}_2\times(n-2)!+{ }_n\mathrm{C}_3\times(n-3)!-\cdots+(-1)^{n-1}{ }_n\mathrm{C}_n\times(n-n)!\]
よって,求める完全順列の総数は,
\[
\begin{align*}
n!-n\left(\bigcup^n_{i=1}A_i\right)=~&n!-\left({ }_n\mathrm{C}_1\times (n-1)!-{ }_n\mathrm{C}_2\times(n-2)!+{ }_n\mathrm{C}_3\times(n-3)!-\cdots+(-1)^{n-1}{ }_n\mathrm{C}_n\times(n-n)!\right)\\
=~&n!-\left(\frac{n!}{1!}-\frac{n!}{2!}+\frac{n!}{3!}-\cdots+(-1)^{n-1}\frac{n!}{n!} \right)\\
=~&n!-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+\cdots+(-1)^{n}\frac{n!}{n!} \\
=~&n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^{n}\frac{1}{n!}\right)\\
=~&n!\sum^{n}_{k=0}\frac{(-1)^k}{k!}\\
\end{align*}
\]
となります.

実験してみましょう.\(n=5\)と代入してみます.
\[
\begin{align*}
5!\sum^{5}_{k=0}\frac{(-1)^k}{k!}&=5!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}\right)\\
&=5\cdot 4\cdot 3-5\cdot 4 +5-1\\
&=60-20+5-1\\
&=44
\end{align*}
\]

おっけい!

© 2022 佐々木数学塾, All rights reserved.