包除原理
数え上げの原理の1つ。複数の集合があったとして、そのどれかに属する要素の数が知りたい場合に用いる。平たくいうと、和集合のサイズを積集合のサイズから求める式。
たとえば3つの集合$ A, B, Cがあったとして、それぞれの集合のサイズと互いの積集合のサイズが分かっているとする。このとき$ \left|A\cup B \cup C\right| = |A| + |B| + |C| - |A\cap B| - |B\cap C| - |A\cap C| + |A\cap B \cap C|となる。
これを一般化すると任意の集合の集合$ U = \{U_i\}があったとき、それらの和集合のサイズは次式で求められる。
$ \left|\bigcup_i U_i\right| = \sum_{S \in 2^U} (-1)^{|S|-1}\left|\bigcap_{s \in S}s\right|
ここで$ 2^Uは$ Uのべき集合。
一般に整数の倍数のように積集合が簡単に求められる場合に用いる。