包除原理

以上の2つの有限集合 A, B に対する包除原理は次のように表せる。

同様に、3つの有限集合 A, B, C に対する包除原理は次のように表せる。


一般に、 n 個の有限集合 A1, ..., An が与えられたとき、その和集合に属する元の数は

と表せる。ただし、ここで [n] = {1, 2, …, n} とした。

この原理の名称は、あらゆるものを「含め」、その後で「取り除いて」補正をするという考え方に基づいていることからきている。n > 2 のとき、共通部分の補正項を計算するのが非常に困難になることもある。また、公式には符号が交互にあらわれる。

この公式はアブラーム・ド・モアブルによるものと考えられているが、ジェームス・ジョセフ・シルベスターまたはアンリ・ポアンカレによるとも言われる。

証明
包除原理を一般に証明するため、X を A1, ..., An の上位集合とする。公式はまず恒等式

を指示関数の変形でもとめ、全ての x ∈ X について足しあわせることで示される。

その他の形
この原理は時に以下のような形で表される。有限集合 S のべき集合 2S 上で定義された関数 f, g が

を満たすならば、

この形は半順序集合 2S の隣接代数におけるメビウスの反転公式となる。

また、包除原理は確率においても以下のように用いられる。

によれば、この公式の始めの k 項の和は左辺の上界と下界を交互にとる：

このことは公式全体が扱いにくい場合に利用される。

応用
おそらく、包除原理のもっともよく知られている応用は、組み合わせ問題における有限集合の攪乱(derangement)に対するものであろう。集合Aの攪乱とはAから自分自身への全単射であって不動点を持たないもののことである。包除原理によって、Aの基数（要素数）をnとしたときの攪乱の数が

となることを示せる。ここで[x]はもっとも近い整数をあたえる関数(nearest integer function)を表す。

これはnのsubfactorialとしても知られ、と表す。
これはまた、全ての全単射に等しい確率が与えられた場合、無作為に選ばれた全単射が攪乱となっている確率がnの増加に従い、1/e に素早く近づくことを示している。

この原理によって理論的な公式を求める場合（特にエラトステネスの篩を用いる素数の数え上げ）、誤差評価が困難であるため有効な公式が得られないことが多い。これは、各項が個別には正確に求められてもそれらの相殺の様子を一般的に定式化することが難しい上に、和の項数が非常に多くなってしまうためである。数論において、ヴィーゴ・ブルンはこのような困難を部分的に克服する方法を見出し、これは現代的な篩の理論の端緒となった。ただし、この理論を用いてもたいてい、厳密な公式はもとより漸近公式さえ得られるのもまれで、したがってふるい落とされた集合の大きさの評価を与えるにとどまる。

共通部分の計算
包除原理とド・モルガンの法則とを合わせることで、共通部分の要素数を計算できる。 を普遍集合、各  について  とし、 が  に関する  の補集合を表すものとする。このとき

をえる。こうして、共通部分をもとめる問題を和集合をもとめる問題に帰着させることができる。

 脚注 

 参考文献 




 関連項目 

完全順列
集合
集合論
ベン図

 外部リンク 




Category:組合せ論
Category:数学の原理
Category:数学に関する記事