15.9 包除則

いくつかの集合の和集合の大きさはどうしたら求められるだろうか？ 例えば、\(60\) 人が数学を専攻し、\(200\) 人が電子情報工学を専攻し、\(40\) 人が物理学を専攻しているとする。このとき、いずれかの専攻に所属する学生は全部で何人だろうか？ \(M\) を数学専攻の学生全体の集合、\(E\) を電子情報工学専攻の学生全体の集合、\(P\) を物理学専攻の学生全体の集合とすれば、計算したいのは \(|M \cup E \cup P|\) である。

加算則からは、もし \(M\), \(E\), \(P\) が共通要素を持たないなら、次の等式が成り立つと分かる:

しかし、集合 \(M\), \(E\), \(P\) は共通要素を持つ可能性がある。例えば、数学と物理学の両方を専攻する学生がいてもおかしくない。そういった学生は上記の等式の右辺で \(2\) 回 (まず \(M\) の要素として \(1\) 回、そして \(P\) の要素としてもう \(1\) 回) カウントされてしまう。さらに悪いことに、数学・電子情報工学・物理学を全て専攻する学生¹は \(3\) 回もカウントされる！

本書で紹介する最も複雑な数え上げ規則は、共通要素を持つ可能性のある任意個の集合が与えられたとき、その和集合の要素数を与える。その規則を表明する前に、まずは簡単な特殊ケースを考えて感覚を掴んでおこう: これから集合が二つのケースと三つケースのケースを考える。

15.9.1 二つの集合の和集合

二つの集合 \(S_{1}\), \(S_{2}\) に対する包除則 (inclusion-exclusion rule) は、和集合 \(S_{1} \cup S_{2}\) の要素数を与える:

直感的には、右辺の第一項が \(S_{1}\) の各要素をカウントし、第二項が \(S_{2}\) の各要素をカウントする。このとき \(S_{1}\) と \(S_{2}\) の両方に属する要素は \(2\) 回カウントされるので、最後の第三項がその分を打ち消す。

15.9.2 三つの集合の和集合

数学、電子情報工学、物理学のいずれかを専攻する学生は何人だろうか？ 言い換えれば、次の等式が成り立つとき \(|M \cup E \cup P|\) の値はいくつだろうか？

三つの集合の和集合の要素数は、より複雑な包除則の公式によって与えられる:

意外なことに、この等式の右辺は \(S_{1}\), \(S_{2}\), \(S_{3}\) に属する各要素をちょうど \(1\) 回ずつカウントする。例えば、\(x\) が三つの集合全てに含まれるとしよう。このとき \(x\) は \(|S_{1}|\), \(|S_{2}|\), \(|S_{3}|\) で \(3\) 回カウントされ、\(|S_{1} \cap S_{2}|\), \(|S_{2} \cap S_{3}|\), \(|S_{3} \cap S_{1}|\) で \(3\) 回打ち消され、最後に \(|S_{1} \cap S_{2} \cap S_{3}|\) で \(1\) 回カウントされる。このため、最終的に \(x\) は \(1\) 回だけカウントされる。

\(x\) が二つの集合に含まれる場合はどうなるだろうか？ 例えば \(x\) を含む集合が \(S_{1}\) と \(S_{2}\) なら、\(x\) は \(|S_{1}|\), \(|S_{2}|\) で \(2\) 回カウントされ、\(|S_{1} \cap S_{2}|\) で \(1\) 回打ち消される。この場合は \(x \notin S_{3}\) なので、他の項は全て \(0\) となる。

上述の等式から分かるように、\(|M \cup E \cup P|\) を求めるには様々な共通部分の要素数が必要になる。そこで、次のように仮定する:

このとき \(|M \cap E| = 4 + 2 \), \(|M \cap P| = 3 + 2\), \(|E \cap P| = 11 + 2\), \(|M \cap E \cap P| = 2\) が成り立つ。これらの値を等式に代入すれば、次の値を得る:

15.9.3 \(42\), \(04\), \(60\) のいずれかを含む数列

集合 \(\left\{ 0, 1, \ldots, 9 \right\}\) の置換の中で、\(4\) と \(2\)、\(0\) と \(4\)、\(6\) と \(0\) のいずれかが連続して並ぶ (言い換えれば、コンマを省略して書いたとき \(42\), \(04\), \(60\) のいずれかを含む) ものはいくつあるだろうか？ 例えば、次の置換は条件を満たさない:

末尾の \(06\) はカウントされない: \(60\) の順番である必要がある。一方で、次の置換は \(04\) と \(60\) の両方を含む:

\(42\) を含む置換全体の集合を \(P_{42}\) として、\(P_{60}\), \(P_{04}\) も同様に定義する。例えば、上記の置換は \(P_{60}\) と \(P_{04}\) の両方に含まれ、\(P_{42}\) には含まれない。求めたいのは \(|P_{42} \cup P_{04} \cup P_{60}|\) の値である。

まず、\(P_{42}\), \(P_{60}\), \(P_{04}\) の要素数をそれぞれ計算しよう。この計算で使えるトリックがある: 例えば \(P_{60}\) を考えるときは、連続する \(6\) と \(0\) を一つの記号として扱うと要素数が簡単に計算できる。このとき、\(6\) と \(0\) が連続する \(\left\{ 0, 1, \ldots, 9 \right\}\) の置換から次の集合の置換への全単射が明らかに存在する:

この全単射による対応関係の例を次に示す:

\(60\) を含む集合の置換は \(9!\) 個あるので、全単射則より \(|P_{60}| = 9!\) を得る。同様の議論から \(|P_{04}| = |P_{42}| = 9!\) も分かる。

続いて、\(P_{42} \cap P_{60}\) などの二集合の和集合を求めよう。同様のトリックを使うと、この和集合から次の集合の置換全体の集合への全単射が存在すると分かる:

よって \(|P_{42} \cap P_{60}| = 8!\) が成り立つ。また、次の集合の置換を考えれば \(|P_{60} \cap P_{04}| = 8!\) を得る:

同様の議論から \(|P_{42} \cap P_{04}| = 8!\) も分かる。最後に、次の集合の置換全体への全単射から \(|P_{60} \cap P_{04} \cap P_{42}| = 7!\) が分かる:

以上の結果を等式に代入すれば次を得る:

15.9.4 \(n\) 個の集合の和集合

\(n\) 個の集合の和集合の要素数は次の規則で与えられる:

これまでに見た集合が \(2\) 個および \(3\) 個のケースの等式は、この一般的な包除則の特殊ケースである。

上記の包除則の表現は理解しやすく、数学的な記号を使った表現と同程度に正確でもある。ただ、数学的な記号を使った表現が以降で必要になるので、それも示しておく。上記の表現を翻訳していけば得られる。

まず、「それぞれの集合の要素数の和」を簡潔に表現する記法は既に知っている。総和が利用できる:

続いて、「異なる \(2\) 集合の和集合」は \(i \neq j\) に対する \(S_{i} \cap S_{j}\) に等しい。ただ、\(S_{i} \cap S_{j}\) と \(S_{j} \cap S_{i}\) は等しいので、\(i < j\) を仮定してカウントを \(1\) 回だけにする必要がある。よって「異なる \(2\) 集合の共通部分の要素数の和」は次の総和で表現できる:

同様に、「\(3\) 集合の共通部分の要素数の和」は次の総和に等しい:

また、包除則の等式で和の各項に付いている互い違いの符号は \((-1)^{n-1}\) で表現できる。これでようやく、数学的な記号を使ったバージョンの包除則が手に入った:

この総和の和としての表現は多くの場面で有用となるものの、共通部分に含まれる集合の個数ごとに項を分ける必要がない場面もある。そのときは次の表現を利用できる:

高校レベルの代数だけを使った包除則の証明を問題 15.59 に示してある。

こういった代数にうんざりし始めているなら、良いニュースがある。次節では、代数を一切使わずにゴツい等式を証明する手法を学ぶ。冗談に聞こえるかもしれないが、数行の議論で複雑な等式が証明できる。