15.1 別の集合を利用した数え上げ

混雑した部屋にいる人の数はどうすれば数えられるだろうか？まず、頭を数える方法が考えられる。人は頭をちょうど一つ持つので、頭の数は人数に等しい。あるいは、耳を数えて \(2\) で割る方法もある。もちろん、この場合は海賊に耳を切られた人や耳を三つ持って産まれた人を考慮しなければならない。これは特定の集合の要素数を数えるとき、別の集合を利用する手法の例である。数え上げで中心的な役割を果たす手法であり、最も簡単な問題から最も難しい問題まで幅広い問題を解くのに利用される。実は、この手法の例は以前に定理 4.5.5 で見ている。これは \(n\) 要素集合の部分集合の個数が長さ \(n\) のビット列の個数と等しいと主張する定理であり、両者の間の全単射を示すことで証明された。

特定の集合の要素数を数えるときに別の集合を利用する最も単純な方法は、両者の間の全単射を見つけることである: 二つの集合の間に全単射が存在するなら、その二つの集合は同じ要素数を持つ。この重要な事実は全単射則 (bijection rule) と呼ばれることが多い。全単射則は定理 4.5.4で触れた写像則 (mapping rule) の一種でもある。

15.1.1 全単射則

全単射則があると、数え上げ可能な集合が増える: ある集合の要素数が分かれば、その集合からの全単射が存在する数多くの集合の要素数も直ちに分かる。例えば、第 III 部の冒頭では次の二つの集合に言及した:

\[ \begin{aligned} A &= \text{\(5\) 種類のドーナツから \(12\) 個を選ぶ方法の個数} \\ B &= \text{ちょうど \(4\) 個の \(1\) を含む長さ \(16\) のビット列の個数} \end{aligned} \]

次に示すのは、集合 \(A\) に属する要素の例を表す記号列である:

\[ \underbrace{00}_{\text{チョコ}} \qquad \underbrace{\quad}_{\text{レモン}} \qquad \underbrace{000000}_{\text{シュガー}} \qquad \underbrace{00}_{\text{グレーズ}} \qquad \underbrace{00}_{\text{プレーン}} \]

ここではドーナツを \(0\) で表し、種類の異なるドーナツの間には空白を入れている。つまり、上記の要素は \(2\) 個のチョコドーナツ、\(0\) 個のレモンドーナツ、\(6\) 個のシュガードーナツ、\(2\) 個のグレーズドーナツ、\(2\) 個のプレーンドーナツを表す。この記号列の空白を \(1\) で表してみよう:

\[ \underbrace{00}_{\text{チョコ}} \quad 1 \quad \underbrace{\quad}_{\text{レモン}} \quad 1 \quad \underbrace{000000}_{\text{シュガー}} \quad 1 \quad \underbrace{00}_{\text{グレーズ}} \quad 1 \quad \underbrace{00}_{\text{プレーン}} \]

この表現で空白は意味を持たないので、詰めて書くことができる:

\[ 0011000000100100 \]

\(4\) 個の \(1\) を持つ長さ \(16\) のビット列が得られた ── \(B\) の要素である！

この例から、\(A\) から \(B\) への全単射が示唆される。\(12\) 個のドーナツの内訳が次の通りだとする:

\[ \text{チョコレート \(c\) 個、レモン \(l\) 個、シュガー \(s\) 個、グレーズ \(g\) 個、プレーン \(p\) 個} \]

この \(12\) 個のドーナツを次のビット列に移す写像を考える:

\[ \underbrace{0 \ldots 0}_{c} \quad 1 \quad \underbrace{0 \ldots 0}_{l} \quad 1 \quad \underbrace{0 \ldots 0}_{s} \quad 1 \quad \underbrace{0 \ldots 0}_{g} \quad 1 \quad \underbrace{0 \ldots 0}_{p} \]

このビット列は必ず長さが \(16\) であり、ちょうど \(4\) 個の \(1\) を含む。つまり \(B\) の要素である。さらに、この写像は全単射でもある: それぞれのビット列には \(12\) 個のドーナツの選び方がちょうど一つ対応する。よって全単射則より \(|A| = |B|\) を得る。これを一般化すると、次の補題となる:

補題 15.1.1

\(k\) 種類のドーナツから \(n\) 個を選ぶ方法の個数は、\(n\) 個の \(0\) と \(k - 1\) 個の \(1\) が並んだビット列の個数に等しい。

この例は全単射則の有用性を示している。二つの大きく異なる集合の要素数が等しいことを証明できた ── しかも、二つの集合の正確な要素数は求めていない。一方の集合の要素数が分かれば、もう一方の集合の要素数も直ちに判明する。

全単射を利用するこういった議論を初めて見たなら、なんて賢いテクニックだろうと驚いたかもしれない。しかし、同様の議論はこれから何度も目にするので、すぐに慣れてしまうだろう。