「場合の数」を正確に数えるには、重複なく・漏れなく数える仕組みが必要です。
集合の要素の個数を求める公式（包除原理）は、その仕組みの出発点。
「なぜ引いて足すのか」を原理から理解すれば、複雑な数え上げも怖くありません。
数学I第3章で「集合」を学びました。 ここでは、集合の要素の個数を数えることに焦点を当てます。 有限集合 $A$ の要素の個数を $n(A)$ で表すことにしましょう。
まず、最も基本的な問いから始めます。 2つの集合 $A$ と $B$ があるとき、$A \cup B$（和集合）の要素の個数はいくつでしょうか？
素朴に考えると、$A$ の要素の個数と $B$ の要素の個数を足せばよさそうです。 しかし、$A$ と $B$ に共通の要素がある場合、それを2回数えてしまうことになります。
たとえば、クラス40人のうち「数学が好きな人」の集合 $A$ が25人、「英語が好きな人」の集合 $B$ が20人とします。 $25 + 20 = 45$ ですが、クラスは40人しかいません。 これは「数学も英語も好きな人」（つまり $A \cap B$ の要素）を2回数えてしまったからです。
$n(A) + n(B)$ と計算すると、$A \cap B$（共通部分）に属する要素は $A$ 側でも $B$ 側でも1回ずつ、合計2回数えられます。
実際には1回だけ数えたいので、余分な1回分を引く。これが $n(A \cup B) = n(A) + n(B) - n(A \cap B)$ の意味です。
この「足しすぎた分を引く」という発想が、包除原理の核心です。暗記するのではなく、「なぜ引くのか」を理解してください。
$A$ と $B$ に共通部分がない場合（$A \cap B = \emptyset$）はどうでしょうか。 共通の要素がないので、重複は起きません。したがって単純に足し算で済みます。
$$A \cap B = \emptyset \implies n(A \cup B) = n(A) + n(B)$$これは「和の法則」の集合版です。第6章で学ぶ「場合の数の和の法則」は、まさにこの性質に基づいています。
✕ 誤：「$A$ が25人、$B$ が20人だから、$A \cup B$ は45人」
○ 正：$A \cap B$ が5人なら、$n(A \cup B) = 25 + 20 - 5 = 40$人
共通部分 $A \cap B = \emptyset$ が明示的に保証されていない限り、$n(A \cap B)$ を引く必要があります。「$A$ と $B$ は排反（互いに素）ですか？」と常に自問してください。
一般の場合：
$$n(A \cup B) = n(A) + n(B) - n(A \cap B)$$$A \cap B = \emptyset$ のとき（排反）：
$$n(A \cup B) = n(A) + n(B)$$この公式は英語で inclusion-exclusion principle（包除原理）と呼ばれます。 inclusion（含める）とは各集合の個数を足すこと、exclusion（除く）とは共通部分を引くことです。
18世紀のフランスの数学者ド・モアブル（Abraham de Moivre）やスイスのオイラー（Leonhard Euler）が 確率論の問題で体系的に用いたのが始まりとされています。 現代の組合せ論やコンピュータサイエンスでも、数え上げの基本定理として頻繁に登場します。
Section 1で学んだ $n(A \cup B) = n(A) + n(B) - n(A \cap B)$ を、具体的な問題で使ってみましょう。 包除原理の使い方を身につけるうえで大切なのは、 どの集合を $A$、$B$ に設定するかを自分で決める力です。
1から100までの自然数のうち、3の倍数または5の倍数であるものの個数を求めてみましょう。
$A$ を「3の倍数の集合」、$B$ を「5の倍数の集合」とすると、求めるのは $n(A \cup B)$ です。
Step 1：各集合の個数を求める。
$n(A) = \left\lfloor \dfrac{100}{3} \right\rfloor = 33$（3, 6, 9, ..., 99）
$n(B) = \left\lfloor \dfrac{100}{5} \right\rfloor = 20$（5, 10, 15, ..., 100）
Step 2：共通部分 $A \cap B$ を求める。
3の倍数かつ5の倍数は、$\text{lcm}(3, 5) = 15$ の倍数です。
$n(A \cap B) = \left\lfloor \dfrac{100}{15} \right\rfloor = 6$（15, 30, 45, 60, 75, 90）
Step 3：包除原理を適用。
$n(A \cup B) = 33 + 20 - 6 = 47$
結論：3の倍数または5の倍数は47個。
ここで注意すべきは、「3の倍数かつ5の倍数」を $A \cap B$ として正しく特定することです。 3と5の最小公倍数が15であるという事実が、$A \cap B$ の計算に使われています。
包除原理を使う問題では、何を集合 $A$、$B$ とするかを自分で決めます。
この「集合の設定」さえ正しくできれば、あとは公式に当てはめるだけです。 逆に、集合の設定を誤ると、問題全体が破綻します。
目安：「○○または△△」と問われたら、○○の集合と△△の集合を設定し、和集合を求める。 「○○かつ△△」は共通部分です。
倍数の問題では、$N$ 以下の正の整数のうち $k$ の倍数の個数が頻繁に必要になります。 これは $k, 2k, 3k, \ldots$ と続くので、$N$ を $k$ で割った商（小数点以下切り捨て）に等しくなります。
$$\text{$N$ 以下の $k$ の倍数の個数} = \left\lfloor \frac{N}{k} \right\rfloor$$「200以上400以下の整数のうち3の倍数の個数」のように、始点が1でない場合は注意が必要です。
✕ 誤：$\left\lfloor \dfrac{400}{3} \right\rfloor = 133$ がそのまま答え
○ 正：$\left\lfloor \dfrac{400}{3} \right\rfloor - \left\lfloor \dfrac{199}{3} \right\rfloor = 133 - 66 = 67$
「400以下の3の倍数」から「199以下の3の倍数」を引きます。始点を $m$ とするなら、$m - 1$ 以下の個数を引くのがポイントです。
2つの集合の包除原理を理解したら、次は3つの集合 $A$, $B$, $C$ の場合です。 $n(A \cup B \cup C)$ を求める公式は、一見すると複雑に見えますが、 原理は2つの場合と全く同じ「重複の補正」です。
まず $n(A) + n(B) + n(C)$ を計算してみましょう。このとき何が起きるかを追跡します。
2つの集合だけに属する要素（たとえば $A \cap B$ に属するが $C$ には属さない要素）： $A$ 側で1回、$B$ 側で1回、合計2回数えられます。1回余分です。
3つの集合すべてに属する要素（$A \cap B \cap C$ の要素）： $A$ 側で1回、$B$ 側で1回、$C$ 側で1回、合計3回数えられます。2回余分です。
そこで、2つずつの共通部分 $n(A \cap B)$、$n(B \cap C)$、$n(C \cap A)$ を引きます。 すると、「2つだけに属する要素」の重複は解消されますが、 「3つすべてに属する要素」は3回足されて3回引かれ、0回になってしまいます。 本来は1回数えたいので、もう1回足し戻す必要があります。
包除原理の本質は、和集合のすべての要素をちょうど1回ずつ数えることです。
3集合の場合、各要素が何回数えられるかを追跡すると：
・1つだけに属する要素：$+1$ 回 → 補正不要
・2つに属する要素：$+2 - 1 = 1$ 回 → 共通部分を引いて補正
・3つに属する要素：$+3 - 3 + 1 = 1$ 回 → 引いて足して補正
どの場合も最終的に「1回」になります。これが包除原理の仕組みです。
✕ 誤：$n(A \cup B \cup C) = n(A) + n(B) + n(C) - n(A \cap B) - n(B \cap C) - n(C \cap A) \textcolor{red}{- n(A \cap B \cap C)}$
○ 正：最後の項 $n(A \cap B \cap C)$ は足す（$+$）です。
覚え方：符号は「$+, -, +, -, \ldots$」と交互に変わります。 1つずつの項は $+$、2つずつの項は $-$、3つ全部の項は $+$。 あるいは、「3回足して3回引いたから0になってしまった。1回戻す」と考えてください。
50人の生徒に3科目のテストを実施しました。 数学に合格した生徒が30人、英語に合格した生徒が25人、国語に合格した生徒が20人。 数学と英語の両方に合格した生徒が15人、英語と国語の両方に合格した生徒が10人、 国語と数学の両方に合格した生徒が12人、3科目すべてに合格した生徒が7人。 このとき、少なくとも1科目に合格した生徒は何人でしょうか。
数学、英語、国語の合格者の集合をそれぞれ $A$, $B$, $C$ とすると：
$$n(A \cup B \cup C) = 30 + 25 + 20 - 15 - 10 - 12 + 7 = 45 \text{（人）}$$$n(A \cap B) = 15$ は「数学と英語に合格した人」の人数です。 この15人の中には、3科目すべてに合格した7人も含まれています。
✕ 誤：「数学と英語だけに合格した人が15人」と解釈する
○ 正：「数学と英語の両方に合格した人が15人」。この中に3科目合格者も含まれる。 数学と英語だけに合格した人は $15 - 7 = 8$ 人です。
包除原理の公式で使う $n(A \cap B)$ は、$C$ に属するかどうかを問わない値です。 ベン図で各領域の人数を個別に求めるときには、この違いに注意してください。
$n$ 個の集合 $A_1, A_2, \ldots, A_n$ に対する包除原理は次のように一般化されます：
$$n\!\left(\bigcup_{i=1}^{n} A_i\right) = \sum_{i} n(A_i) - \sum_{i < j} n(A_i \cap A_j) + \sum_{i < j < k} n(A_i \cap A_j \cap A_k) - \cdots$$
$k$ 個の集合の交わりには $(-1)^{k+1}$ の符号がつきます。 項の数は $\binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} = 2^n - 1$ 個です。
大学の組合せ論では、この一般化を用いて完全順列（攪乱順列）の個数や、 オイラーのトーシェント関数（互いに素な整数の個数）を導出します。 さらに進むと、メビウスの反転公式という、包除原理を半順序集合上に拡張した強力な定理に出会います。
全体集合 $U$ の部分集合 $A$ に対して、$A$ の補集合 $\overline{A}$ の要素の個数は：
$$n(\overline{A}) = n(U) - n(A)$$この単純な式が、実は数え上げの最強の武器になります。 「直接数えるのが難しい」ときに、「全体から余事象を引く」というアプローチです。
「少なくとも1つの条件を満たすものの個数」を直接数えるのは、場合分けが複雑になりがちです。
そこで発想を逆転させます。「1つも条件を満たさないもの」を全体から引けば、 それが「少なくとも1つを満たすもの」の個数です。
$$n(\text{少なくとも1つ}) = n(U) - n(\text{1つも満たさない})$$
「少なくとも」という言葉が出たら、補集合を使うシグナルです。
補集合を使った数え上げでは、ド・モルガンの法則が重要な役割を果たします。
$$\overline{A \cup B} = \overline{A} \cap \overline{B}, \qquad \overline{A \cap B} = \overline{A} \cup \overline{B}$$左の式の意味を言葉にすると、「$A$ にも $B$ にも属さない」は「$A$ に属さない、かつ、$B$ に属さない」と同じです。
この法則を使えば、「$A$ にも $B$ にも属さない要素の個数」は次のように求められます：
$$n(\overline{A} \cap \overline{B}) = n(\overline{A \cup B}) = n(U) - n(A \cup B)$$1から100までの自然数のうち、4でも6でも割り切れない数の個数を求めましょう。
$U$ を1から100までの自然数全体の集合、$A$ を4の倍数の集合、$B$ を6の倍数の集合とします。 求めるのは $n(\overline{A} \cap \overline{B})$ です。
ド・モルガンの法則より $\overline{A} \cap \overline{B} = \overline{A \cup B}$ なので：
$$n(\overline{A} \cap \overline{B}) = n(U) - n(A \cup B)$$$n(A) = 25$、$n(B) = 16$、$n(A \cap B) = \left\lfloor \dfrac{100}{12} \right\rfloor = 8$（$\text{lcm}(4,6) = 12$ の倍数）より、
$$n(A \cup B) = 25 + 16 - 8 = 33$$ $$n(\overline{A} \cap \overline{B}) = 100 - 33 = 67$$✕ 誤：4の倍数かつ6の倍数だから $4 \times 6 = 24$ の倍数
○ 正：4の倍数かつ6の倍数は $\text{lcm}(4, 6) = 12$ の倍数
「かつ」は最小公倍数（lcm）であり、単純な積ではありません。 $4 \times 6 = 24$ が最小公倍数になるのは、4と6が互いに素（$\gcd = 1$）の場合だけです。 $\gcd(4, 6) = 2 \neq 1$ なので、$\text{lcm}(4, 6) = \dfrac{4 \times 6}{\gcd(4, 6)} = 12$ です。
「少なくとも1つ」は補集合で対処できますが、「ちょうど $k$ 個の条件を満たす」場合はどうでしょうか。 たとえば「3科目のうちちょうど2科目に合格した人」は、包除原理とベン図を組み合わせて求めます。
ベン図の各領域（Section 5で詳しく扱います）を個別に計算し、 「ちょうど2つに属する領域」を足し上げるのが基本的な方法です。
第7章で学ぶ確率でも、全く同じ発想が使われます。 「少なくとも1回は表が出る確率」は「1回も表が出ない確率」を1から引いて求めます。
$$P(\text{少なくとも1回表}) = 1 - P(\text{全部裏})$$
集合の要素の個数で $n(\overline{A}) = n(U) - n(A)$ を使う技法は、 確率で $P(\overline{A}) = 1 - P(A)$ を使う技法と本質的に同じです。 ここで「補集合を使う」感覚を身につけておくと、確率の学習がスムーズになります。
包除原理の公式は強力ですが、問題によってはベン図を使って各領域の個数を直接求めるほうが見通しがよい場合があります。 特に、3つの集合で「ちょうど○個に属する要素」を求める問題では、ベン図が威力を発揮します。
3つの集合 $A$, $B$, $C$ のベン図には、$A$, $B$, $C$ の内側/外側の組み合わせで $2^3 - 1 = 7$ つの非空な領域が生じます（外側を含めると8領域）。 各領域の要素の個数を $a$, $b$, $c$, $d$, $e$, $f$, $g$ とおくと、以下のように対応します：
| 領域 | 属する集合 | 個数 |
|---|---|---|
| $A$ のみ | $A$ に属し、$B$, $C$ には属さない | $a$ |
| $B$ のみ | $B$ に属し、$A$, $C$ には属さない | $b$ |
| $C$ のみ | $C$ に属し、$A$, $B$ には属さない | $c$ |
| $A \cap B$ のみ | $A$, $B$ に属し、$C$ には属さない | $d$ |
| $B \cap C$ のみ | $B$, $C$ に属し、$A$ には属さない | $e$ |
| $C \cap A$ のみ | $C$, $A$ に属し、$B$ には属さない | $f$ |
| $A \cap B \cap C$ | $A$, $B$, $C$ すべてに属する | $g$ |
このとき、問題文で与えられる値との関係は次のようになります：
ベン図を使うときの鉄則は、内側から外側へ順番に求めることです。
Step 1：最も内側の $g = n(A \cap B \cap C)$ を書き込む。
Step 2：2つずつの共通部分から $g$ を引いて、$d$, $e$, $f$ を求める。
Step 3：各集合の個数から内側の値を引いて、$a$, $b$, $c$ を求める。
Step 4：全体集合からすべてを引いて、外側の個数を求める。
✕ 誤：$n(A) = 30$ だから「$A$ のみの領域」が30人 → 他の領域と合計が全体を超える
○ 正：$n(A) = 30$ は $A$ 全体（$a + d + f + g$）の人数。「$A$ のみ」の $a$ は $30 - d - f - g$ で求める
$n(A)$ は「$A$ に属する全員」であり、$B$ や $C$ との共通部分も含んでいます。 必ず内側（$g$ → $d, e, f$ → $a, b, c$）の順で求めてください。
応用的な問題として、「$n(A \cap B)$ の最大値・最小値を求めよ」という問題があります。 全体集合 $U$ の中で $n(A)$, $n(B)$, $n(U)$ が与えられたとき、 共通部分の個数は一意に定まりません。ベン図を使って範囲を考えます。
$n(A \cap B)$ は次の範囲に収まります：
$$\max(0, \, n(A) + n(B) - n(U)) \leq n(A \cap B) \leq \min(n(A), n(B))$$最大：$A$ と $B$ ができるだけ重なっている場合。小さい方が大きい方に完全に含まれれば、$n(A \cap B) = \min(n(A), n(B))$。
最小：$A$ と $B$ ができるだけ離れている場合。ただし $n(A) + n(B) > n(U)$ なら、 全体に収まりきらないので必ず重なりが生じます。
包除原理は、大学数学ではメビウスの反転公式（Mobius inversion formula）として一般化されます。
自然数の約数関係のような「半順序集合」の上で、ある関数 $f$ から別の関数 $g$ を復元する公式です。 整数論では、オイラーのトーシェント関数 $\varphi(n)$ が「$n$ 以下で $n$ と互いに素な正整数の個数」ですが、 これは包除原理（メビウス関数）を使って導出されます：
$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$
ここで積は $n$ の素因数 $p$ 全体にわたります。 高校で学ぶ包除原理は、この壮大な理論体系のほんの入口です。
Q1. $n(A) = 15$, $n(B) = 20$, $n(A \cap B) = 8$ のとき、$n(A \cup B)$ を求めてください。
Q2. 包除原理で $n(A \cap B)$ を「引く」のはなぜですか？ 理由を説明してください。
Q3. 3つの集合の包除原理で、$n(A \cap B \cap C)$ の項の符号は $+$ と $-$ のどちらですか？
Q4. 「少なくとも1つの条件を満たす」個数を求めるとき、補集合をどう使いますか？
Q5. 1から60までの自然数のうち、4の倍数でも6の倍数でもない数の個数を求めてください。
この記事で学んだ内容を、入試形式の問題で確認しましょう。
1から200までの自然数のうち、3の倍数または7の倍数であるものの個数を求めよ。
$85$ 個
方針：3の倍数の集合を $A$、7の倍数の集合を $B$ として包除原理を適用する。
$n(A) = \left\lfloor \dfrac{200}{3} \right\rfloor = 66$
$n(B) = \left\lfloor \dfrac{200}{7} \right\rfloor = 28$
$A \cap B$ は $\text{lcm}(3, 7) = 21$ の倍数の集合（3と7は互いに素なので $\text{lcm} = 3 \times 7$）。
$n(A \cap B) = \left\lfloor \dfrac{200}{21} \right\rfloor = 9$
$n(A \cup B) = 66 + 28 - 9 = 85$
1から100までの自然数のうち、4でも7でも割り切れない整数の個数を求めよ。
$64$ 個
方針：「4でも7でも割り切れない」はド・モルガンの法則より $\overline{A \cup B}$ に対応。全体から引く。
$A$ を4の倍数、$B$ を7の倍数の集合とする。$n(U) = 100$。
$n(A) = 25$、$n(B) = 14$、$n(A \cap B) = \left\lfloor \dfrac{100}{28} \right\rfloor = 3$（$\text{lcm}(4,7) = 28$）
$n(A \cup B) = 25 + 14 - 3 = 36$
$n(\overline{A} \cap \overline{B}) = n(\overline{A \cup B}) = 100 - 36 = 64$
50人の生徒が3科目（数学・英語・国語）の試験を受けた。数学に合格した生徒は30人、英語に合格した生徒は25人、国語に合格した生徒は20人であった。また、数学と英語の両方に合格した生徒は15人、英語と国語の両方に合格した生徒は8人、国語と数学の両方に合格した生徒は12人、3科目すべてに合格した生徒は5人であった。
(1) 少なくとも1科目に合格した生徒は何人か。
(2) 1科目も合格しなかった生徒は何人か。
(3) ちょうど2科目に合格した生徒は何人か。
(1) $45$ 人 (2) $5$ 人 (3) $20$ 人
方針：数学、英語、国語の合格者の集合を $A$, $B$, $C$ として、3集合の包除原理を適用する。
(1) $n(A \cup B \cup C) = 30 + 25 + 20 - 15 - 8 - 12 + 5 = 45$（人）
(2) $n(U) - n(A \cup B \cup C) = 50 - 45 = 5$（人）
(3) ベン図の各領域を内側から求める。$g = n(A \cap B \cap C) = 5$。
$d = n(A \cap B) - g = 15 - 5 = 10$（数学と英語のみ）
$e = n(B \cap C) - g = 8 - 5 = 3$（英語と国語のみ）
$f = n(C \cap A) - g = 12 - 5 = 7$（国語と数学のみ）
ちょうど2科目に合格した生徒は $d + e + f = 10 + 3 + 7 = 20$（人）
100人にアンケートを行ったところ、旅行先 $A$ に行ったことがある人は80人、旅行先 $B$ に行ったことがある人は70人であった。$A$ と $B$ の両方に行ったことがある人の人数の最大値と最小値を求めよ。
最大値 $70$ 人、最小値 $50$ 人
方針：$n(A \cap B)$ のとりうる範囲を、$n(A \cup B) \leq n(U)$ と $n(A \cap B) \geq 0$ の条件から求める。
$n(A \cup B) = n(A) + n(B) - n(A \cap B) = 80 + 70 - n(A \cap B) = 150 - n(A \cap B)$
最大値：$A \cap B$ が最大になるのは、小さい方の集合 $B$ が $A$ に完全に含まれる場合。$n(A \cap B) \leq \min(n(A), n(B)) = 70$。 このとき $n(A \cup B) = 150 - 70 = 80 \leq 100$。条件を満たすので、最大値は $70$ 人。
最小値：$n(A \cup B) \leq n(U) = 100$ より、$150 - n(A \cap B) \leq 100$。 したがって $n(A \cap B) \geq 50$。最小値は $50$ 人。
⚠️ 検算：$n(A \cap B) = 50$ のとき $n(A \cup B) = 100$。全員がどちらかに行ったことがある状態。 $A$ だけが30人、$B$ だけが20人、両方が50人で、$30 + 20 + 50 = 100$。✓