包除原理
Contents
包除原理とは
包除原理 (読：ほうじょげんり, 英：inclusion-exclusion principle) とは、一つ以上の有限集合からなる合併集合の要素数を、共通部分を利用して求める定理のこと。
\[ \begin{aligned} \Bigg|\bigcup_{i=1}^n A_i\Bigg| &= \sum_{k=1}^n\left[(-1)^{k-1}\sum_{I\sube[n] ~|I|=k}\Bigg|\bigcap_{i\in I}A_i\Bigg|\right] \end{aligned} \]
包除原理の証明：
次式を仮定する。
\[ \begin{aligned} \Bigg|\bigcup_{i=1}^n A_i\Bigg| &= \sum_{k=1}^n\left[(-1)^{k-1}\sum_{I\sube[n], ~|I|=k}\Bigg|\bigcap_{i\in I}A_i\Bigg|\right] \end{aligned} \]
一つの有限集合からなる合併集合の要素数は、
\[ \begin{aligned} \Bigg|\bigcup_{i=1}^1 A_i\Bigg| &= \sum_{k=1}^1\left[(-1)^{k-1}\sum_{I\sube[1], ~|I|=k}\Bigg|\bigcap_{i\in I}A_i\Bigg|\right] \cr |A_1| &= |A_1| \end{aligned} \tag{1} \]
となり、仮定が成立する。
次に $n+1$ つの有限集合からなる合併集合の要素数を求める。この有限集合の要素数は、
\[ \begin{aligned} \Bigg|\bigcup_{i=1}^{n+1}A_i\Bigg| &={} \Bigg|\bigcup_{i=1}^{n}A_i\cup A_{n+1}\Bigg| \cr &={} \Bigg|\bigcup_{i=1}^{n}A_i\Bigg| + |A_{n+1}| - \Bigg|\bigcup_{i=1}^{n}A_i\cap A_{n+1}\Bigg| \end{aligned} \tag{2} \]
と展開できる。ここで右辺の第一項は仮定より、
\[ \begin{aligned} \Bigg|\bigcup_{i=1}^n A_i\Bigg| &= \sum_{k=1}^n\left[(-1)^{k-1}\sum_{I\sube[n], ~|I|=k}\Bigg|\bigcap_{i\in I}A_i\Bigg|\right] \cr &= \sum_{i=1}^n|A_i| \cr &\quad - \sum_{1\le i_1\lt i_2}^n|A_{i_1}\cap A_{i_2}| \cr &\quad + \sum_{1\le i_1\lt i_2\lt i_3}^n|A_{i_1}\cap A_{i_2}\cap A_{i_3}| \cr &\qquad \vdots \cr &\quad + (-1)^{n-1}\Bigg|\bigcap_{i=1}^n A_i\Bigg| \cr \end{aligned} \tag{3} \]
右辺の第三項は仮定より、
\[ \begin{aligned} \Bigg|\bigcup_{i=1}^{n}A_i\cap A_{n+1}\Bigg| &= \sum_{k=1}^n\left[(-1)^{k-1}\sum_{I\sube[n], ~|I|=k}\Bigg|\bigcap_{i\in I}(A_i\cap A_{n+1})\Bigg|\right] \cr &= \sum_{i=1}^n|A_i\cap A_{n+1}| \cr &\quad - \sum_{1\le i_1\lt i_2}^n|A_{i_1}\cap A_{i_2}\cap A_{n+1}| \cr &\quad + \sum_{1\le i_1\lt i_2\lt i_3}^n|A_{i_1}\cap A_{i_2}\cap A_{i_3}\cap A_{n+1}| \cr &\qquad \vdots \cr &\quad + (-1)^{n-1}\Bigg|\bigcap_{i=1}^n A_i\cap A_{n+1}\Bigg| \cr \end{aligned} \tag{4} \]
$(3)$ から $(4)$ を一項ずらして差を取ると、
\[ \begin{aligned} \Bigg|\bigcup_{i=1}^n A_i\Bigg| -& \Bigg|\bigcup_{i=1}^{n}A_i\cap A_{n+1}\Bigg| \cr &= \sum_{i=1}^n|A_i| \cr &\quad - \sum_{1\le i_1\lt i_2}^n|A_{i_1}\cap A_{i_2}| - \sum_{i_1=1}^n|A_{i_1}\cap A_{n+1}| \cr &\quad + \sum_{1\le i_1\lt i_2\lt i_3}^n|A_{i_1}\cap A_{i_2}\cap A_{i_3}| + \sum_{1\le i_1\lt i_2}^n|A_{i_1}\cap A_{i_2}\cap A_{n+1}| \cr &\qquad \vdots \cr &\quad + (-1)^{n-1}\sum_{I\sube [n], ~|I|=n}\Bigg|\bigcap_{i\in I} A_i\Bigg| - (-1)^{n-2}\sum_{J\sube [n], ~|J|=n-1}\Bigg|\bigcap_{j\in J} A_j\cap A_{n+1}\Bigg| \cr &\quad - (-1)^{n-1}\sum_{J\sube [n], ~|J|=n}\Bigg|\bigcap_{j\in J} A_j\cap A_{n+1}\Bigg| \cr \cr \Bigg|\bigcup_{i=1}^n A_i\Bigg| -& \Bigg|\bigcup_{i=1}^{n}A_i\cap A_{n+1}\Bigg| \cr &= \sum_{i=1}^n|A_i| \cr &\quad - \sum_{1\le i_1\lt i_2}^{n+1}|A_{i_1}\cap A_{i_2}| \cr &\quad + \sum_{1\le i_1\lt i_2\lt i_3}^{n+1}|A_{i_1}\cap A_{i_2}\cap A_{i_3}| \cr &\qquad \vdots \cr &\quad + (-1)^{n-1}\sum_{I\sube [n+1], ~|I|=n}\Bigg|\bigcap_{i\in I} A_i\Bigg| \cr &\quad + (-1)^{n}\sum_{I\sube [n+1], ~|I|=n+1}\Bigg|\bigcap_{i\in I} A_i\Bigg| \cr \end{aligned} \tag{5} \]
$(2),(5)$ より、
\[ \begin{aligned} \Bigg|\bigcup_{i=1}^{n}A_i\Bigg| +& |A_{n+1}| - \Bigg|\bigcup_{i=1}^{n}A_i\cap A_{n+1}\Bigg| \cr &= \sum_{i=1}^n|A_i| + |A_{n+1}| \cr &\quad - \sum_{1\le i_1\lt i_2}^{n+1}|A_{i_1}\cap A_{i_2}| \cr &\quad + \sum_{1\le i_1\lt i_2\lt i_3}^{n+1}|A_{i_1}\cap A_{i_2}\cap A_{i_3}| \cr &\qquad \vdots \cr &\quad + (-1)^{n-1}\sum_{I\sube [n+1], ~|I|=n}\Bigg|\bigcap_{i\in I} A_i\Bigg| \cr &\quad + (-1)^{n}\sum_{I\sube [n+1], ~|I|=n+1}^n\Bigg|\bigcap_{i\in I} A_i\Bigg| \cr &= \sum_{i=1}^{n+1}|A_i| \cr &\quad - \sum_{1\le i_1\lt i_2}^{n+1}|A_{i_1}\cap A_{i_2}| \cr &\quad + \sum_{1\le i_1\lt i_2\lt i_3}^{n+1}|A_{i_1}\cap A_{i_2}\cap A_{i_3}| \cr &\qquad \vdots \cr &\quad + (-1)^{n-1}\sum_{I\sube [n+1], ~|I|=n}\Bigg|\bigcap_{i\in I} A_i\Bigg| \cr &\quad + (-1)^{(n+1)-1}\sum_{I\sube [n+1], ~|I|=n+1}\Bigg|\bigcap_{i\in I} A_i\Bigg| \cr &= \sum_{k=1}^{n+1}\left[(-1)^{k-1}\sum_{I\sube[n+1], ~|I|=k}\Bigg|\bigcap_{i\in I}A_i\Bigg|\right] \end{aligned} \tag{6} \]
$(1),(6)$ から、数学的帰納法により、$n$ つの有限集合からなる合併集合の要素数は次式より導かれる。
\[ \therefore{} \Bigg|\bigcup_{i=1}^n A_i\Bigg| = \sum_{k=1}^n\left[(-1)^{k-1}\sum_{I\sube[n] ~|I|=k}\Bigg|\bigcap_{i\in I}A_i\Bigg|\right] \]