# 包除原理 ## 定義 包除原理(Inclusion-Exclusion、規則14.9.1)は、互いに素とは限らない集合の和集合のサイズを求める一般公式である。2集合の場合 $|S_1 \cup S_2| = |S_1| + |S_2| - |S_1 \cap S_2|$、3集合の場合 $|S_1\cup S_2\cup S_3| = |S_1|+|S_2|+|S_3| - |S_1\cap S_2|-|S_1\cap S_3|-|S_2\cap S_3| + |S_1\cap S_2\cap S_3|$ という具体例から出発し、一般のn集合について「個々の集合のサイズの和から、2つ組の交差のサイズの和を引き、3つ組の交差のサイズの和を足し、…」という交代和で和集合のサイズが得られることを主張する。記号的には $\left|\bigcup_{i=1}^n S_i\right| = \sum_{\emptyset\neq I\subseteq\{1,\dots,n\}} (-1)^{|I|+1}\left|\bigcap_{i\in I} S_i\right|$ と表される。証明の骨子は、和集合に属する各要素がこの交代和の中で正味ちょうど1回だけ数えられることを確認することにある(例えば3集合全てに属する要素は、単項3回分の加算・2つ組3回分の減算・3つ組1回分の加算により正味1回だけ数えられる)。応用として、10個の数字の順列のうち特定の隣接パターン(42, 04, 60)を含むものの個数を求める例、および第8章で証明なしに述べられたEulerのφ関数の明示公式 $\varphi(n) = n\prod_{i=1}^m(1-1/p_i)$(nの素因数分解が$p_1^{e_1}\cdots p_m^{e_m}$のとき)の証明がある。後者は、$[0,n)$の整数のうちnと互いに素でないものの集合を、各素因数の倍数集合の和集合として捉え、その大きさを包除原理で計算することで得られる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.9) ## 横断的知見 - 第8章(Number Theory)は Euler のφ関数の明示公式 $\varphi(n)=n\prod_i(1-1/p_i)$ を系8.10.11として**証明なしに**提示する(合同算術・RSAの文脈でこの式を既知の事実として使う)。第14章はまさにこの式を、包除原理という独立した数え上げの道具を使って初めて証明する(§14.9.5)。両章を突き合わせると、第8章では応用上必要な結果として天下り的に導入された式が、第14章で数論とは独立した組合せ論的な論拠(集合の和集合のサイズの計算)によって裏付けられるという、証明の「後回し」と「回収」の関係が明確になる。これは、本書が数論(第8章)と数え上げ(第14章)という異なる部を横断して同一の定理を扱う数少ない例であり、複数の部にまたがる定理の依存関係を示す具体例になっている。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] 系8.10.11, [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.9.5) ## 未解決の問い - 包除原理は集合の個数nが増えるにつれて項数が指数的に増加する($2^n-1$個の非空部分集合)ため、実用上はnが小さい場合や、交差のサイズに規則性がある場合(Eulerのφ関数の例のように、交差のサイズが素因数の積の形で簡潔に書ける場合)に限って有効である。交差のサイズを効率よく評価できない一般の場合への近似的・確率的な拡張(Bonferroni不等式など)は本章では扱われていない。 - 包除原理の各項の符号 $(-1)^{|I|+1}$ と、二項係数([[二項係数]])の交代和(二項定理で $a=1, b=-1$ とした場合の $\sum_k (-1)^k\binom{n}{k}=0$)との関係は、本章では明示的に論じられていない。両者はともに交代和の構造を持つため、突き合わせられる余地がある。 ## 関連 - 概念: [[数え上げ]] / [[鳩の巣原理]] / [[二項係数]] / [[合同算術]](Eulerのφ関数の定義) / [[素数]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 14 §14.9.