包除原理
包除原理（ほうじょげんり、）あるいは包含と排除の原理とは、数え上げ組合せ論における基本的な結果のひとつ。特別な場合には「有限集合 "A" と "B" の和集合に属する元の数を計算するには、まずそれぞれに属する元の数 |"A"| と |"B"| を足しあわせた後、それらの共通部分に属する元の数 |"A" ∩ "B"| を引き去ればよい」というものである。つまり単に数え上げた後で重複を取り除くことに相当する。
以上の2つの有限集合 "A", "B" に対する包除原理は次のように表せる。
同様に、3つの有限集合 "A", "B", "C" に対する包除原理は次のように表せる。
一般に、 "n" 個の有限集合 "A"1, ..., "A""n" が与えられたとき、その和集合に属する元の数は
と表せる。ただし、ここで ["n"] = {1, 2, …, "n"} とした。
この原理の名称は、あらゆるものを「含め」、その後で「取り除いて」補正をするという考え方に基づいていることからきている。"n" &gt; 2 のとき、共通部分の補正項を計算するのが非常に困難になることもある。また、公式には符号が交互にあらわれる。
この公式はアブラーム・ド・モアブルによるものと考えられているが、ジェームス・ジョセフ・シルベスターまたはアンリ・ポアンカレによるとも言われる。