完全順列(その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*}
\]

おっけい!

包除原理

数学Aで次の式を学びました.

\[
\begin{align*}
n(A_1 \cup A_2)=&n(A_1)+n(A_2)\\
&-n(A_1 \cap A_2)
\end{align*}
\]

\[
\begin{align*}
n(A_1 \cup A_2 \cup A_3)=&n(A_1)+n(A_2)+n(A_3)\\
&-n(A_1 \cap A_2)-n(A_1 \cap A_3)-n(A_2 \cap A_3)\\
&+n(A_1 \cap A_2 \cap A_3)
\end{align*}
\]

授業でベン図を用いて理解したことと思います.

この2つの式の流れ的に,

\[
\begin{align*}
&n(A_1 \cup A_2 \cup A_3 \cup A_4)\\
=&~n(A_1)+n(A_2)+n(A_3)+n(A_4)\\
&-n(A_1 \cap A_2)-n(A_1 \cap A_3)-n(A_1 \cap A_4)-n(A_2 \cap A_3)-n(A_2 \cap A_4)-n(A_3 \cap A_4)\\
&+n(A_1 \cap A_2 \cap A_3)+n(A_1 \cap A_2 \cap A_4)+n(A_1 \cap A_3 \cap A_4)+n(A_2 \cap A_3 \cap A_4)\\
&-n(A_1 \cap A_2 \cap A_3 \cap A_4)\\
\end{align*}
\]

などが,そしてさらに一般化して,

\[
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\bigcup_{i}^{n} A_i\)は\[A_1 \cup A_2 \cup ~\cdots~ \cup A_n\]を,\(\displaystyle\sum_{i<j}^{n}n(A_i \cap A_j)\)などは\(1\leq i<j\leq n~(i,j\in \mathbb{N})\)をみたす\(n(A_i \cap A_j)\)をすべて加えたものを意味するとします.

さて,この予想は正しいのでしょうか??もはやベン図では太刀打ちできません.数学的帰納法で証明してみます.

証明

\(n=l\)のとき予想が正しいとします.この仮定のもとで,\(n=l+1\)のときを考えます.

\[
\begin{align*}
n\left(\displaystyle\bigcup_{i}^{l+1} A_i\right)&=n\left(\left(\displaystyle\bigcup_{i}^{l}A_i\right)\bigcup A_{l+1}\right)\\
&=n\left(\displaystyle\bigcup_{i}^{l}A_i\right)+n\left(A_{l+1}\right)-n\left(\left(\displaystyle\bigcup_{i}^{l}A_i\right) \bigcap A_{l+1}\right)
\end{align*}
\]

ここで,第三項にある\(\left(\displaystyle\bigcup_{i}^{l}A_i\right) \bigcap A_{l+1}\)について考えてみると,

\[
\begin{align*}
&\left(\displaystyle\bigcup_{i}^{l}A_i\right) \bigcap A_{l+1}\\
=&(A_1 \cup A_2 \cup A_3 \cup \cdots \cup A_l)\cap A_{l+1}\\
=&(A_1 \cap A_{l+1} ) \cup (A_2 \cap A_{l+1} ) \cup (A_3 \cap A_{l+1} ) \cup \cdots \cup(A_l \cap A_{l+1} )\\
=&\bigcup^{l}_i(A_i \cap A_{l+1})
\end{align*}
\]

ですから,

\[n\left(\displaystyle\bigcup_{i}^{l+1} A_i\right)=n\left(\displaystyle\bigcup_{i}^{l}A_i\right)+n\left(A_{l+1}\right)-n\left(\bigcup^{l}_i(A_i \cap A_{l+1})\right)\quad \cdots(\ast)\]

を得ます.ここで仮定より,

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

また,この式の\(A_i\)を\(A_i \cap A_{l+1}\)に変えることにより,

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

これら仮定を\((\ast)\)に代入すると,

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

となって\(n=l+1\)のときも成り立つことが分かります.\(n=1\)のとき成り立つことは自明.(証明終)

見た目はいかついですが高校レベルでも理解できる内容(未習の知識としては\(\bigcup\)の記法と「または,かつ」の分配法則くらい)なので,ぜひ証明にチャレンジしてみてください.集合,場合の数,数学的帰納法,\(\Sigma\)記号の使い方などの総復習にもなりますから.

ちなみに今回証明した式を包除原理と呼びます.