15.2 列の数え上げ

全単射則を使うと、何かを数え上げる問題を別の何かを数え上げることで解けるようになる。ここから一般的な戦略が示唆される: 特定のものを数え上げる方法だけを詳しく学んでおいて、他のものを数え上げるときは全単射則を使えばいい！この戦略は本書でも採用される。具体的には、これから様々な列 (sequence) を数え上げる方法を学ぶ。他の集合 \(T\) の要素数を求める必要があるときは、まず \(T\) から何らかの列の集合 \(S\) への全単射を見つける。その上で列を数え上げる超ニンジャ的スキルを使って \(|S|\) を求めれば、同時に \(|T|\) も分かる。もちろん、議論を進める中で磨きをかける必要はあるものの、基本的なアイデアは本当にこれだけである！

15.2.1 乗算則

乗算則 (product rule) は集合の直積の要素数を与える。復習しておくと、集合 \(P_{1}\), \(P_{2}\), \(\ldots\), \(P_{n}\) の直積

\[ P_{1} \times P_{2} \times \cdots \times P_{n} \]

は列の集合であり、それぞれの列の第 \(1\) 要素は\(P_{1}\) から取られ、第 \(2\) 要素は \(P_{2}\) の要素から取られ、以下同様となる。

規則 15.2.1[乗算則 (product rule)]

\(P_{1}\), \(P_{2}\), \(\ldots\) \(P_{n}\) が有限集合なら、次の等式が成り立つ:

\[ |P_{1} \times P_{2} \times \cdots \times P_{n}| = |P_{1}| \cdot |P_{2}| \cdots |P_{n}| \]

例えば、毎日の朝食を集合 \(B\) から一つ選び、昼食を集合 \(L\) から一つ選び、夕食を集合 \(D\) から一つ選ぶとする:

\[ \begin{aligned} B &= \left\{ \text{パンケーキ},\, \text{ベーコンエッグ},\, \text{ベーグル},\, \text{ドリトス} \right\} \\ L &= \left\{ \text{ハンバーガーとポテト},\, \text{ガーデンサラダ},\, \text{ドリトス} \right\} \\ D &= \left\{ \text{マカロニ},\, \text{ピザ},\, \text{冷食ブリトー},\, \text{パスタ},\, \text{ドリトス} \right\} \end{aligned} \]

このとき \(B \times L \times D\) は可能な一日の食事を並べた列全体の集合である。例えば、次のような列が含まれる:

\[ \begin{gathered} (\text{パンケーキ},\, \text{ハンバーガーとポテト},\, \text{ピザ}) \\ (\text{ベーコンエッグ},\, \text{ガーデンサラダ},\, \text{パスタ}) \\ (\text{ドリトス},\, \text{ドリトス},\, \text{冷食ブリトー}) \end{gathered} \]

乗算則を使えば、一日の食事の献立が何通りあるかを計算できる:

\[ \begin{aligned} |B \times L \times D| &= |B| \cdot |L| \cdot |D| \\ &= 4 \cdot 3 \cdot 5 \\ &= 60 \end{aligned} \]

15.2.2 \(n\) 要素集合の部分集合の個数

定理 4.5.5 の証明では、\(n\) 要素集合の部分集合全体の集合から長さ \(n\) のビット列全体の集合への全単射を構築した。つまり、\(n\) 要素集合の部分集合の個数を求める問題が、長さ \(n\) のビット列の個数を求める問題に等しいと示した ── まさに計画通り！そのとき省略した、長さ \(n\) のビット列が \(2^{n}\) 個存在する理由を説明しよう: これはビット列全体の集合が直積として定義される事実から分かる:

\[ \left\{ 0, 1 \right\}^{n} ::= \underbrace{\left\{ 0, 1 \right\} \times \left\{ 0, 1 \right\} \times \cdots \times \left\{ 0, 1 \right\}}_{n \text{ 個}} \]

乗算則を使えば答えが求まる:

\[ \left|\left\{ 0, 1 \right\}^{n}\right| = \left|\left\{ 0, 1 \right\}\right|^{n} = 2^{n} \]

15.2.3 加算則

Bartバートは妹の Lisaリサに不機嫌になっていい日を \(20\) 日、怒りっぽくなっていい日を \(40\) 日、無愛想になっていい日を \(60\) 日だけ割り当てた。Lisa が良い子にならなくていいのは何日間だろうか？ Lisa が不機嫌になる日全体の集合、怒りっぽくなる日全体の集合、不愛想になる日全体の集合をそれぞれ \(C\), \(I\), \(S\) とすれば、この質問の答えは \(|C \cup I \cup S|\) に等しい。彼女が三つの状態のうち一つにしか同時になれないと仮定すれば、この値は次の加算則 (sum rule) を使って計算できる:

規則 15.2.2[加算則 (sum rule)]

集合 \(A_{1}\), \(A_{2}\), \(\ldots\), \(A_{n}\) が共通要素を持たないなら、次の等式が成り立つ:

\[ \left| A_{1} \cup A_{2} \cup \cdots \cup A_{n} \right| = \left| A_{1} \right| + \left| A_{2} \right| + \cdots + \left| A_{n} \right| \]

よって、Lisa が良い子にならなくていい日数は次のように求められる:

\[ \begin{aligned} | C \cup I \cup S| &= |C| + |I| + |S| \\ &= 20 + 40 + 60 \\ &= 120 \end{aligned} \]

加算則は共通部分を持たない集合の和集合に対してだけ成り立つ点に注意してほしい。共通部分を持つ集合の要素数を求める問題はこれより複雑であり、第 15.9 節で議論される。

15.2.4 パスワードの数え上げ

数え上げの問題が単一の規則だけで解けることはまずない。全単射則、乗算則、加算則および他の手法を総動員して初めて解答が求まる問題も多くある。

パスワード、電話番号、自動車のナンバープレートが関係する問題では、乗算則が有用になる場合が多い。例えば、あるコンピューターシステムでは正当なパスワードが \(6\) 文字以上 \(8\) 文字以下の記号列であり、それぞれの記号は大文字および小文字のアルファベットまたは数字だと仮定する。さらに、パスワードの一文字目はアルファベットである必要があり、二文字目以降には制限がないとする。このとき、正当なパスワードは何通り存在するだろうか？

次のように二つの集合 \(F\), \(S\) を定義する。\(F\) に属する記号はパスワードの一文字目に使用でき、\(S\) に属する記号は二文字目以降に使用できる:

\[ \begin{aligned} F &= \left\{ a, b, \ldots, z, A, B, \ldots, Z \right\} \\ S &= \left\{ a, b, \ldots, z, A, B, \ldots, Z, 0, 1, \ldots, 9 \right\} \end{aligned} \]

これらの集合を使うと、正当なパスワード全体の集合は次のように表現できる¹:

\[ (F \times S^{5}) \cup (F \times S^{6}) \cup (F \times S^{7}) \]

例えば、\(6\) 文字のパスワードは全て \(F \times S^{5}\) に含まれ、\(7\) 文字のパスワードは全て \(F \times S^{6}\) に含まれ、\(8\) 文字のパスワードは全て \(F \times S^{7}\) に含まれる。これらの集合は共通部分を持たないので、加算則と乗算則を使えば正当なパスワードの総数を計算できる:

\[ \begin{aligned} & |(F \times S^{5}) \cup (F \times S^{6}) \cup (F \times S^{7})| && \\ &\qquad = |F \times S^{5}| + |F \times S^{6}| + |F \times S^{7}| && (\text{加算則}) \\ &\qquad = |F| \cdot |S|^{5} + |F| \cdot |S|^{6} + |F| \cdot |S|^{7} && (\text{乗算則}) \\ &\qquad = 52 \cdot 62^{5} + 52 \cdot 62^{6} + 52 \cdot 62^{7} && \\ &\qquad \approx 1.8 \cdot 10^{14} && \end{aligned} \]

\(S^{5}\) は \(S \times S \times S \times S \times S\) を意味する。\(S^{6}\) や \(S^{7}\) も同様となる。 ↩︎