「包除原理」は、集合の要素数を正確に数えるための重要な原理です。基本的な使い方から応用問題まで、高校生向けに丁寧に解説していきます。
目次
包除原理とは
包除原理（Inclusion-Exclusion Principle）は、複数の集合が重なっているときに、全体の要素数を正確に数える方法です。2つまたは3つ以上の集合に共通する部分を「引いたり足したり」して数を調整します。
例えば、2つの集合 \( A \), \( B \) の和集合の要素数は次のようになります：
\[ |A \cup B| = |A| + |B| – |A \cap B| \]3つの集合 \( A \), \( B \), \( C \) の場合：
これを一般に \( n \) 個の集合に拡張したのが「一般形の包除原理」です。
基本例題
問題：あるクラスで英語が得意な生徒が20人、数学が得意な生徒が15人、両方得意な生徒が5人いる。このとき、少なくともどちらかが得意な生徒は何人か？
解答：
\[ |E \cup M| = |E| + |M| – |E \cap M| = 20 + 15 – 5 = 30 \]よって、少なくともどちらかが得意な生徒は30人です。
応用例題①：整数の倍数を含む数の個数
問題：1から100までの整数のうち、2または3または5の倍数であるものは何個あるか？
解答：
まず、それぞれの倍数の個数を数えます。 – 2の倍数：\(\left\lfloor \frac{100}{2} \right\rfloor = 50\) – 3の倍数：\(\left\lfloor \frac{100}{3} \right\rfloor = 33\) – 5の倍数：\(\left\lfloor \frac{100}{5} \right\rfloor = 20\) 次に、重複部分を引きます。 – \(2 \cap 3 = 6\)の倍数：\(\left\lfloor \frac{100}{6} \right\rfloor = 16\) – \(3 \cap 5 = 15\)の倍数：\(\left\lfloor \frac{100}{15} \right\rfloor = 6\) – \(2 \cap 5 = 10\)の倍数：\(\left\lfloor \frac{100}{10} \right\rfloor = 10\) 最後に、3つ全ての倍数（30の倍数）を足します。 – \(2 \cap 3 \cap 5 = 30\)：\(\left\lfloor \frac{100}{30} \right\rfloor = 3\) まとめて包除原理を適用： \[ 50 + 33 + 20 – 16 – 10 – 6 + 3 = 74 \]よって、2または3または5の倍数は 74個 です。
応用例題②：重複しないパスワードの個数
問題：0〜9の数字を使って4桁の暗証番号を作る。ただし、各桁に同じ数字を使ってはいけないとする。このとき、2または3または4を含むパスワードは何通りあるか？
解答：まず、重複のない4桁の番号の総数は：
\[ {}_{10}P_4 = 10 \times 9 \times 8 \times 7 = 5040 \]次に、「2も3も4も含まない」パスワードを考え、それを全体から引きます。
– 使用可能な数字：0〜9 から 2, 3, 4 を除いた 7個（0, 1, 5, 6, 7, 8, 9） – その7個から重複なしで4桁選ぶ：\({}_{7}P_4 = 7 \times 6 \times 5 \times 4 = 840\) したがって、2または3または4を少なくとも1つ含むパスワード数は： \[ 5040 – 840 = 4200 \]応用例題③：条件を満たす順列
問題：1〜5の数字を並べて作る5桁の数で、2または4が先頭に来るものは何通りあるか？
解答：全て異なる5つの数字から作る順列の数は：
\[ 5! = 120 \]まず、2が先頭に来る場合：
– 残りは1, 3, 4, 5の4つ → \({}_{4}P_4 = 4! = 24\) 同様に、4が先頭に来る場合も24通り。 ただし、「2と4の両方が先頭」は不可能なので、重複はなし。 \[ 24 + 24 = 48 \]よって、答えは 48通り。
まとめ
- 包除原理は、重複を適切に処理するための強力なツール
- 応用範囲は広く、整数問題・順列・パスワードの組合せなどさまざまな場面に登場
- 「少なくとも〜を満たす」問題では、補集合を使って包除原理を適用するのが有効
包除原理は難しく感じるかもしれませんが、構造がわかれば非常にパワフルな武器になります。ぜひ、例題を通して慣れていきましょう！
