包除原理

内容

有限集合 $A_1,\dots,A_n$ に対し、$\Big|\bigcup_{i=1}^n A_i\Big| = \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1}|A_1 \cap \cdots \cap A_n|$ が成り立つ。

なぜ正しいのか?

重なり合う集合の大きさを単純に足し合わせると、複数の集合に属する元は重複して数えられてしまう。二つずつの共通部分を引くことでこの重複を修正できるが、今度は三つずつの共通部分が引きすぎになるので、それを足し戻す必要があり、以下同様に、和集合のすべての元がちょうど一回ずつ数えられるまで符号を交互に変えていく。

この定理を使うトピック

関連する定理

ステップごとの証明

この定理のステップごとの証明はまだありません。