15.4 除算則
「耳の数を数えて \(2\) で割る」は部屋にいる人の数を数えるアプローチとして馬鹿げているものの、数え上げの強力な手法の例である。
\(k\) 対 \(1\) の関数 (\(k\)-to-\(1\) function) とは、終域の任意の要素の逆像が \(k\) 要素集合であるような関数を意味する。例えば、(典型的な) 人間の耳を人間に対応付ける関数は \(2\) 対 \(1\) の関数である。同様に、手の指を人間に対応付ける関数は \(10\) 対 \(1\) の関数、手足の指を人間に対応付ける関数は \(20\) 対 \(1\) の関数となる。一般に次の規則が言える:
\(k\) 対 \(1\) の関数 \(f \colon A \to B\) 存在するなら、次の等式が成り立つ:
例えば、\(A\) を部屋の中に存在する耳全体の集合、\(B\) を部屋にいる人全体の集合とすれば、\(A\) から \(B\) への \(2\) 対 \(1\) の関数が存在する。ここから \(|A| = 2 \cdot |B|\) が分かる。変形すれば \(|B| = |A| / 2\) であり、先ほどの例で使った事実が得られる: 人の数は耳の個数の半分に等しい。意外に思うかもしれないが、多くの数え上げ問題は全ての要素を何度も数え上げてから除算則で正しい解答を得るアプローチを使うとずっと簡単になる。いくつか例を見てみよう。
15.4.1 もう一つのチェスの問題
見分けの付かない二つのルークの駒を、行または列を共有しないようにチェス盤に配置する方法は何通りあるだろうか？ 正当な配置の例を図 \(\text{15.2}\) \(\text{(a)}\) に、正当でない配置の例を図 \(\text{15.2}\) \(\text{(b)}\) に示す。
) の配置例: 二つのルークが同じ列にある \(\text{(b)}\) の配置は正当でない。
集合 \(A\) を次のように定める:
そして、正当なルークの配置全体の集合を \(B\) とする。このとき \(A\) から \(B\) への自然な関数 \(f\) が存在する。具体的に言えば、\(f(r_{1}, c_{1}, r_{2}, c_{2})\) は一つのルークを \(r_{1}\) 行 \(c_{1}\) 列に置き、もう一つのルークを \(r_{2}\) 行 \(c_{2}\) 列に置く配置となる。
しかし、この関数には一つ問題がある。次の二つの列を見てほしい:
\(f\) の下で、一つ目の列はルークを左下の隅と右上の隅に置く配置に移される。また、二つ目の列はルークを右上の隅と左下の隅に置く配置に移される。つまり、この二つの列は同じ配置を表現する異なる列である！ 実は、この配置は図 \(\text{15.2}\) \(\text{(a)}\) に示されている。
より一般的に言えば、関数 \(f\) によって任意の正当な配置に移される列は必ずちょうど \(2\) 個ある。言い換えれば \(f\) は \(2\) 対 \(1\) の関数であり、従って除算則から \(|A| = 2 \cdot |B|\) が分かる。この等式を整理すれば、解答 \(|B|\) が計算できる:
最後の式変形では、これまでの問題と同じように一般化された乗算則を使って \(A\) の要素数を計算している。
15.4.2 円卓の騎士
アーサー王が \(n\) 人の騎士を円卓に座らせるとき、その席順は何通りあるだろうか？ どこに誰が座るかを座り方 (seating) と呼び、全ての騎士の両隣の騎士が同じ座り方は等しい席順 (arrangement) を持つとみなすことにする。言い換えれば、騎士 \(1\) から始めて時計回りに座っている騎士を並べた列が同じ座り方は同じ席順を持つ。例えば、次に示す二つの座り方は同じ席順を持つ:
騎士の座り方は真北にある席から時計回りに座っている騎士を並べた列で特定できる。よって座り方は騎士の置換に対応し、\(n!\) 通りの座り方が存在する。騎士の置換と座り方の対応関係の例を次に示す:
二つの座り方が同じ席順を持つのは、円卓を回して騎士 \(1\) が真北に座るようにした場合の座り方が同じときである。例えば \(n = 4\) なら、任意の席順に対して、その席順を持つ異なる座り方がちょうど \(4\) 個存在する。この例を示す:
任意の座り方に対して、全員の座る位置を同じだけ環状に移動させた座り方は同じ席順を持つ。異なる座り方が得られる移動量は \(n\) 個あるので、座り方から席順への写像は実際には \(n\) 対 \(1\) の写像である。よって除算則より、\(n\) 人の騎士が円卓に座るときの席順の個数は次のように計算できる: