包除原理

包除原理は、複数の集合の合併の大きさを、それらの共通部分の大きさの加減を交互に行うことで数え上げるものです。

Definition

有限集合の合併の濃度は、すべての空でない部分集合にわたる、それらのすべての共通部分の濃度の交代和に等しいと述べる計数恒等式。

Scope

このトピックでは、包除原理の公式と、禁止された特性のリストを避けるオブジェクトを数えるためのその応用について説明します。これには、攪乱順列、全射、オイラーのトーシェント関数、および与えられた数と互いに素な整数の数が含まれます。また、篩の視点と、半順序集合上のメビウス関数の一般化が導入され、この原理がより広範な代数的設定に位置づけられます。

Core questions

• 複数の重複する条件のうち、少なくとも1つを満たす要素はいくつありますか？
• 禁止された特性の集合のすべてを避けるオブジェクトをどのように数えることができますか？
• 攪乱順列と全射の計数は、この原理からどのように導き出されますか？
• 半順序集合上のメビウス関数は、包除原理をどのように一般化しますか？

Key concepts

• 重複する集合の合併
• 篩法
• 包除原理による攪乱順列
• 全射の計数
• オイラーのトーシェント関数
• 半順序集合上のメビウス関数

Key theories

包除原理の公式

集合A_1からA_nの合併の濃度は、単一集合の大きさの和からペアワイズの共通部分を引いたものに、トリプル共通部分を足したものなどを交互に加減することで、共有要素の過剰計数を体系的に修正します。

半順序集合上のメビウス反転公式

スタンレーの半順序集合論的一般化は、包除原理の交代符号を半順序集合のメビウス関数に置き換え、この原理を数論的および束論的反転公式と統一します。

Clinical relevance

篩の考え方は、数論（エラトステネスの篩や解析的篩）、確率論（合併確率を制限するボンフェローニの不等式）、および重複する故障モードを持つシステムの信頼性解析に一般化されます。

History

ド・モアブルとシルベスターによって本質的に述べられたこの原理は、1964年にロータによって半順序集合上のメビウス関数の一般理論の中に位置づけられ、現代組み合わせ論の画期的な出来事となりました。

Key figures

• Abraham de Moivre
• Gian-Carlo Rota

Seminal works

• stanley2011

Frequently asked questions

なぜ符号が交互になるのですか？

いくつかの集合に属する要素は何度も加えられすぎます。ペアワイズの共通部分を引くことで過剰に修正されるため、トリプル共通部分が再び加えられ、各要素が正確に一度だけ数えられるような交代パターンが生成されます。

メビウス関数との関連は何ですか？

包除原理は、部分集合のブール束におけるメビウス反転の特殊なケースであり、この場合、メビウス関数はプラスまたはマイナス1の値を取ります。