15.3 一般化された乗算則

この講義を取っている \(n\) 人の中からノーベル賞、日本国際賞、ピューリッツァー賞の受賞者が選ばれるとしたら、何通りの選び方があるだろうか？組み合わせの問題を列に関する問題に変換する戦略を使えば、この問題にも簡単に答えられる。この講義の受講者 \(n\) 人の集合を \(P\) とすれば、三つの賞の受賞者の選び方全体の集合から \(P^{3} ::= P \times P \times P\) への全単射が存在する。例えば、この全単射で次の選び方は列 \((\text{Barack}, \text{George}, \text{Bill})\) に移される:

Barackバラクがノーベル賞を受賞する。
Georgeジョージが日本国際賞を受賞する。
Billビルがピューリッツァー賞を受賞する。

乗算則から \(|P^{3}| = |P|^{3} = n^{3}\) が分かるので、\(n\) 人の中から受賞者を選ぶ方法は \(n^{3}\) 通りあると結論できる。ここで、\(P^{3}\) には \((\text{Barack}, \text{Bill}, \text{Barack})\) のような一人の人物が複数の賞を受賞する選び方に対応する三つ組が含まれる点に注意してほしい。

では、三つの賞が異なる人物に授与されるとしたら、選び方は何通りになるだろうか？以前と同様に受賞者の選び方を \((\text{Bill}, \text{George}, \text{Barack}) \in P^{3}\) などの三つ組に移す写像を考えることはできるものの、その写像は全単射とならない。例えば、三つ組 \((\text{Barack}, \text{Bill}, \text{Barack})\) に移される受賞者の選び方は存在しない: \(\text{Barack}\) に二つの賞が授与されることは許されていないからである。ただ、次の集合 \(S\) であれば受賞者の選び方全体の集合からの全単射が存在する:

\[ S = \left\{ (x, y, z) \in P^{3} \; | \; x, y, z \text{ は異なる人物} \right\} \]

よって、問題は \(S\) の要素数を求める問題に帰着される。ただ残念ながら、\(S\) に属する列は要素の間に依存関係 (「全て異なる」) があるので、\(S\) の要素数は乗算則で計算できない。しかし、この数え上げ問題を解くには乗算則に少しだけ磨きをかければ十分である:

規則 15.3.1[一般化された乗算則 (generalized product rule)]

\(S\) を長さ \(k\) の列の集合とする。\(S\) に属する列が次の条件を満たすとする:

第 \(1\) 要素の選択肢は \(n_{1}\) 個ある。
先頭の \(1\) 要素が決まったとき、第 \(2\) 要素の選択肢は \(n_{2}\) 個ある。
先頭の \(2\) 要素が決まったとき、第 \(3\) 要素の選択肢は \(n_{3}\) 個ある。
\(\vdots\)
先頭の \(k - 1\) 要素が決まったとき、第 \(k\) 要素の選択肢は \(n_{k}\) 個ある。

このとき次の等式が成り立つ:

\[ |S| = n_{1} \cdot n_{2} \cdot n_{3} \cdots n_{k} \]

先ほどの問題における \(S\) の要素は列 \((x, y, z)\) であり、一つ目の賞の受賞者 \(x\) を選ぶ方法は \(n\) 通り存在し、\(x\) の選び方のそれぞれに対して二つ目の賞の受賞者 \(y\) を選ぶ方法が \(n - 1\) 通り存在する (\(x\) 以外の人物を選べるため)。さらに、三つ目の賞の受賞者 \(z\) は \(x\) と \(y\) 以外の人物である必要があるので、その選び方は \(n - 2\) 通り存在する。よって一般化された乗算則より、\(n\) 人の中から三つの賞の受賞者を選ぶ方法の個数は次の値に等しい:

\[ |S| = n \cdot (n - 1) \cdot (n - 2) \]

15.3.1 無効なドル紙幣

ドル紙幣に印字された \(8\) 桁のシリアル番号に同じ数字が含まれるなら、そのドル紙幣は無効 (defective) だと誰かが言った。自分の財布を確認してみてほしい。この意味で「無効」なドル紙幣がとても多いことに気が付くだろう。では、同様の意味で「有効」なドル紙幣はどれくらいの割合で存在するのだろうか？シリアル番号の各桁には全ての一桁の数字が同じ確率で含まれると仮定すれば、この質問の解答は次のように計算できる:

\[ \text{有効なドル紙幣の割合} = \frac{|\left\{ \text{各桁が全て異なるシリアル番号} \right\}|}{|\left\{ \text{シリアル番号} \right\}|} \tag{15.1}\]

まず分母を計算しよう。ここでは制限がない: \(1\) 桁目には \(10\) 個の選択肢があり、\(2\) 桁目には \(10\) 個の選択肢があり、\(3\) 桁目には \(10\) 個の選択肢があり、以下同様となる。よって乗算則より \(8\) 桁のシリアル番号は全部で \(10^{8}\) 個ある。

続いて分子を計算しよう。同じ数字を異なる桁に使ってはいけないので、\(1\) 桁目には \(10\) 個の選択肢があり、\(2\) 桁目には \(9\) 個の選択肢があり、\(3\) 桁目には \(8\) 個の選択肢があり、以下同様となる。よって、一般化された乗算則を使えば各桁が全て異なるシリアル番号の個数を計算できる:

\[ 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 = \frac{10!}{2} = 1{,}814{,}400 \]

二つの値を等式 \(\text{(15.1)}\) に代入すれば次の結論を得る:

\[ \text{有効なドル紙幣の割合} = \frac{1{,}814{,}400}{100{,}000{,}000} = 1.8144\% \]

15.3.2 チェスの問題

ポーン (\(P\))、ナイト (\(K\))、ビショップ (\(B\)) の駒を、同じ列または行に存在する駒が存在しないようにチェス盤に配置する方法は何通りあるだろうか？三つの駒の正当な配置の例を図 \(\text{15.1}\) \(\text{(a)}\) に、正当でない配置の例を図 \(\text{15.1}\) \(\text{(b)}\) に示す。

図 15.1ポーン ()、ナイト ()、ビショップ () の配置例: ビショップとナイトが同じ行にある \(\text{(b)}\) の配置は正当でない。

まず、このチェス駒の配置に関する問題を列に関する問題に言い換えよう。正当な駒の配置全体の集合から次の形をした列全体の集合への全単射が存在する:

\[ (r_{P}, c_{P}, r_{N}, c_{N}, r_{B}, c_{B}) \]

ここで \(r_{P}\), \(r_{N}\), \(r_{B}\) は異なる行を、\(c_{P}\), \(c_{N}\), \(c_{B}\) は異なる列を表す。具体的に言えば、この列に対応する配置ではポーンが \(r_{P}\) 行 \(c_{P}\) 列に、ナイトが \(r_{N}\) 行 \(c_{N}\) 列に、ビショップが \(r_{B}\) 行 \(c_{B}\) 列に配置される。この形をした列の個数は一般化された乗算則で計算できる:

\(r_{P}\) の選択肢は \(8\) 個ある。
\(c_{P}\) の選択肢は \(8\) 個ある。
\(r_{N}\) の選択肢は \(7\) 個ある (\(r_{P}\) を選択できない)。
\(c_{N}\) の選択肢は \(7\) 個ある (\(c_{P}\) を選択できない)。
\(r_{B}\) の選択肢は \(6\) 個ある (\(r_{P}\) と \(r_{N}\) を選択できない)。
\(c_{B}\) の選択肢は \(6\) 個ある (\(c_{P}\) と \(c_{N}\) を選択できない)。

よって、正当な配置は全部で \((8 \cdot 7 \cdot 6)^{2}\) 個ある。

15.3.3 置換

集合 \(S\) の置換 (permutation) とは、\(S\) の全ての要素をちょうど一度ずつ含む列を言う。例えば、集合 \(\left\{ a, b, c \right\}\) の置換は \(6\) 個ある:

\[ \begin{gathered} (a, b, c) \qquad (a, c, b) \qquad (b, a, c) \\ (b, c, a) \qquad (c, a, b) \qquad (c, b, a) \end{gathered} \]

\(n\) 要素集合の置換はいくつあるだろうか？これまでと同様に考えると、第 \(1\) 要素の選択肢は \(n\) 個ある。第 \(1\) 要素の選択のそれぞれに対して、第 \(2\) 要素の選択肢は \(n - 1\) 個ある。さらに、先頭の \(2\) 要素をどのように選択したとしても、第 \(3\) 要素の選択肢は \(n - 2\) 個ある。以下同様だから、\(n\) 要素集合の置換の個数は次のように計算できる:

\[ n \cdot (n - 1) \cdot (n - 2) \cdots 3 \cdot 2 \cdot 1 = n! \]

この事実を使って計算すれば、\(3\) 要素集合 \(\left\{ a, b, c \right\}\) の置換は \(3! = 6\) 個ある。これは先ほど示した事実と一致する。

置換は本講義で約 \(1600\) 兆回ほど言及される。実は、\(n!\) を近似する Stirling の公式 (定理 14.5.1) を紹介した大きな理由は、置換の個数が \(n!\) で表されるためである:

\[ n! \sim \sqrt{2 n \pi } \left( \frac{n}{e} \right)^{\! n} \]