blue271828's misc :-)

包除原理

#組合せ論

Contents

包除原理とは

包除原理 (読：ほうじょげんり, 英：inclusion-exclusion principle) とは、一つ以上の有限集合からなる合併集合の要素数を、共通部分を利用して求める定理のこと。

∣⋃i=1nAi∣=∑k=1n[(−1)k−1∑I⊆[n] ∣I∣=k∣⋂i∈IAi∣] \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}


包除原理の証明：

次式を仮定する。

∣⋃i=1nAi∣=∑k=1n[(−1)k−1∑I⊆[n], ∣I∣=k∣⋂i∈IAi∣] \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}

一つの有限集合からなる合併集合の要素数は、

∣⋃i=11Ai∣=∑k=11[(−1)k−1∑I⊆[1], ∣I∣=k∣⋂i∈IAi∣]∣A1∣=∣A1∣(1) \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+1n+1 つの有限集合からなる合併集合の要素数を求める。この有限集合の要素数は、

∣⋃i=1n+1Ai∣=∣⋃i=1nAi∪An+1∣=∣⋃i=1nAi∣+∣An+1∣−∣⋃i=1nAi∩An+1∣(2) \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}

と展開できる。ここで右辺の第一項は仮定より、

∣⋃i=1nAi∣=∑k=1n[(−1)k−1∑I⊆[n], ∣I∣=k∣⋂i∈IAi∣]=∑i=1n∣Ai∣−∑1≤i1<i2n∣Ai1∩Ai2∣+∑1≤i1<i2<i3n∣Ai1∩Ai2∩Ai3∣⋮+(−1)n−1∣⋂i=1nAi∣(3) \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}

右辺の第三項は仮定より、

∣⋃i=1nAi∩An+1∣=∑k=1n[(−1)k−1∑I⊆[n], ∣I∣=k∣⋂i∈I(Ai∩An+1)∣]=∑i=1n∣Ai∩An+1∣−∑1≤i1<i2n∣Ai1∩Ai2∩An+1∣+∑1≤i1<i2<i3n∣Ai1∩Ai2∩Ai3∩An+1∣⋮+(−1)n−1∣⋂i=1nAi∩An+1∣(4) \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)(3) から (4)(4) を一項ずらして差を取ると、

∣⋃i=1nAi∣−∣⋃i=1nAi∩An+1∣=∑i=1n∣Ai∣−∑1≤i1<i2n∣Ai1∩Ai2∣−∑i1=1n∣Ai1∩An+1∣+∑1≤i1<i2<i3n∣Ai1∩Ai2∩Ai3∣+∑1≤i1<i2n∣Ai1∩Ai2∩An+1∣⋮+(−1)n−1∑I⊆[n], ∣I∣=n∣⋂i∈IAi∣−(−1)n−2∑J⊆[n], ∣J∣=n−1∣⋂j∈JAj∩An+1∣−(−1)n−1∑J⊆[n], ∣J∣=n∣⋂j∈JAj∩An+1∣∣⋃i=1nAi∣−∣⋃i=1nAi∩An+1∣=∑i=1n∣Ai∣−∑1≤i1<i2n+1∣Ai1∩Ai2∣+∑1≤i1<i2<i3n+1∣Ai1∩Ai2∩Ai3∣⋮+(−1)n−1∑I⊆[n+1], ∣I∣=n∣⋂i∈IAi∣+(−1)n∑I⊆[n+1], ∣I∣=n+1∣⋂i∈IAi∣(5) \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)(2),(5) より、

∣⋃i=1nAi∣+∣An+1∣−∣⋃i=1nAi∩An+1∣=∑i=1n∣Ai∣+∣An+1∣−∑1≤i1<i2n+1∣Ai1∩Ai2∣+∑1≤i1<i2<i3n+1∣Ai1∩Ai2∩Ai3∣⋮+(−1)n−1∑I⊆[n+1], ∣I∣=n∣⋂i∈IAi∣+(−1)n∑I⊆[n+1], ∣I∣=n+1n∣⋂i∈IAi∣=∑i=1n+1∣Ai∣−∑1≤i1<i2n+1∣Ai1∩Ai2∣+∑1≤i1<i2<i3n+1∣Ai1∩Ai2∩Ai3∣⋮+(−1)n−1∑I⊆[n+1], ∣I∣=n∣⋂i∈IAi∣+(−1)(n+1)−1∑I⊆[n+1], ∣I∣=n+1∣⋂i∈IAi∣=∑k=1n+1[(−1)k−1∑I⊆[n+1], ∣I∣=k∣⋂i∈IAi∣](6) \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)(1),(6) から、数学的帰納法により、nn つの有限集合からなる合併集合の要素数は次式より導かれる。

∴∣⋃i=1nAi∣=∑k=1n[(−1)k−1∑I⊆[n] ∣I∣=k∣⋂i∈IAi∣] \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]

関連記事

Tags

#Ansible (3) #Bash (1) #Docker (1) #Git (2) #Hugo (2) #Molecule (1) #Python (1) #WSLtty (1) #アルゴリズム (4) #ビジネス用語 (1) #プログラミング (1) #位相空間論 (8) #初等数学 (20) #初等関数 (1) #実解析 (1) #幾何学 (3) #微分積分学 (18) #情報理論 (4) #抽象代数学 (14) #数理モデル (2) #数理論理学 (21) #機械学習 (3) #正規表現 (1) #測度論 (3) #特殊関数 (4) #確率論 (18) #組合せ論 (5) #統計学 (12) #線型代数学 (18) #複素解析学 (4) #解析学 (15) #論理学 (6) #順序集合論 (9)