集合の要素数の数え上げに関する基本的な公式を紹介します．
和集合の要素数に関する以下の等式を，包除原理といいます．
包除原理： $A_1,A_2,…,A_n$ を有限集合とするとき，次の等式が成り立つ． $$|A_1\cup A_2 \cup \cdots \cup A_n|=\sum_{i=1}^n |A_i|-\sum_{1\le i < j \le n} |A_i\cap A_j|+\sum_{1\le i < j < k \le n} |A_i\cap A_j \cap A_k|-\cdots +(-1)^n |A_1\cap A_2\cap \cdots \cap A_n|$$ ただし，$|X|$ は集合 $X$ の要素の数を表す．
左辺は，$A_1,…,A_n$ の和集合の要素数です．右辺がわかりにくいかもしれません．まず，和の記号の部分ですが，$\sum$ の下にある $1\le i < j \le n$ というのは，『$i,j$ は $i< j$ を満たしながら， $1$ 以上 $n$ 以下の範囲すべてを渡って和をとる』という意味です．たとえば，$n=4$ ならば， $$\sum_{1\le i < j \le 4} |A_i\cap A_j|=|A_1\cap A_2|+|A_1\cap A_3|+|A_1\cap A_4|+|A_2\cap A_3|+|A_2\cap A_4|+|A_3\cap A_4|$$ となります．$1\le i < j < k \le n$ というのも同様です．つまり，右辺に現れる項は，$1$ 個の共通部分，$2$ 個の共通部分，$3$ 個の共通部分，．．．，$n$ 個の共通部分というように，いくつかの共通部分がそれぞれひとつずつ現れます．
そして，右辺の符号は $+$ と $-$ が交互に現れています．
$n=2$ のとき
この場合はよく知られている下の公式になります． $$|A\cup B|=|A|+|B|-|A\cap B|$$
$n=3$ のとき
この場合は，下のような公式になります． $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$ 下のベン図でこの公式を考えてみましょう．
左辺は，色のついた部分全体の要素数にあたります．$|A|+|B|+|C|$ は赤い領域と青い領域と黄色い領域の和です．このとき，重なっている部分は足しすぎているので，$-|A\cap B|-|A\cap C|-|B\cap C|$ で帳尻を合わせようとします．こうすると，今度は $|A\cap B\cap C|$ の部分が完全に引かれてしまうので，最後に $+|A\cap B\cap C|$ をすれば，左辺と一致します．これがベン図による包除原理の考え方です．
$n=3$ の場合で考えた方法を参考にして，包除原理を数え上げと二項定理を用いて証明してみましょう．
証明： $x\in A_1\cup A_2\cup \cdots \cup A_n$ をひとつ選びます．$A_1,…,A_n$ のうち，$x$ を含む集合を $A_{t_1},A_{t_2},…,A_{t_k}$ とします (ただし，$t_1< t_2 < \cdots < t_k$)．示すべき等式の左辺と右辺で要素 $x$ が何回計算されているのか (たし合わせに何回現れるのか)を考えます． 左辺は当然 $1$ 回 $+$ の符号で現れます．以下，右辺を考えます． まず，第一項では，$A_{t_1},A_{t_2},…,A_{t_k}$ を足すときに $x$ を勘定するので，${}_k \mathrm{C} _1$ 回 $+$ の符号で現れます． つぎに，第二項では，共通部分をとる二つの集合がどちらも $A_{t_1},A_{t_2},…,A_{t_k}$ のいずれかであるときに限り $x$ を勘定するので，${}_k \mathrm{C} _2$ 回 $-$ の符号で現れます． 以下同様に考えると，第 $r$ 項 ($1\le r\le n$) では ${}_k \mathrm{C} _r$ 回 $(-1)^{r+1}$ の符号で現れます． したがって，合計の $x$ の計算は， $${}_k \mathrm{C} _1-{}_k \mathrm{C} _2+\cdots +(-1)^{k+1}{}_k \mathrm{C} _k$$ となります．
いっぽう，二項定理より， $$(1-1)^k={}_k \mathrm{C} _0-{}_k \mathrm{C} _1+{}_k \mathrm{C} _2-\cdots +(-1)^k {}_k \mathrm{C} _k$$ であり，${}_k \mathrm{C} _0=1$ を上式に代入して移項すると， $$1={}_k \mathrm{C} _1-{}_k \mathrm{C} _2+\cdots +(-1)^{k+1}{}_k \mathrm{C} _k$$ を得ます．したがって，等式の左辺と右辺の $x$ の計算回数は一致します．$x$ は任意にとってきているので，等式が示されます．
問 $100$ 以下の自然数のうち，$3$ または $5$ の倍数である数はいくつあるか．
$100$ 以下の $3$ の倍数全体の集合を $A$，$100$ 以下の $5$ の倍数全体の集合を $B$ とすると，求めるべきは $|A\cup B|$．
$100=3\times 33+1$ より，$|A|=33$，$100=5\times 20$ より，$|B|=20$ である．$A\cap B$ は $100$ 以下の $15$ の倍数全体の集合で，$100=15\times 6+10$ より，$|A\cap B|=6$．以上から， $$|A\cup B|=|A|+|B|-|A\cap B|=33+20-6=47$$ $47$ 個．
問 $8$ つの異なる色のボールを $3$ つの箱 $a,b,c$ に入れる．どの箱も $1$ つ以上のボールが入っているような入れ方は何通りあるか．
$X$ を$8$ つの異なる色のボールを何の制約もなく $3$ つの箱に入れる入れ方全体の集合とする．
さらに，$A,B,C$ をそれぞれ箱 $a,b,c$ にボールをひとつもいれない入れ方全体の集合とする．求めるべきは， $$|X|-|A\cup B\cup C|$$ である．$|X|=3^8$ である．また，$|A|=|B|=|C|=2^8$，$|A\cap B|=|A\cap C|=|B\cap C|=1$，$|A\cap B \cap C|=0$ より， $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$ $$=3\times 2^8-3+0=3\times 2^8-3$$ よって， $$|X|-|A\cup B\cup C|=3^8-(3\times 2^8-3)=5796$$ $5796$ 通り．
