15.6 重複を許す列の数え上げ

15.6.1 部分集合の列

\(n\) 要素集合の \(k\) 要素部分集合を一つ選ぶ操作は、同じ \(n\) 要素集合を二つの部分集合で分割する操作に等しい: 一つの部分集合は \(k\) 個の要素を持ち、もう一つの部分集合は残りの \(n - k\) 個の要素を持つ。よって、部分集合則 (規則 15.5.1) はそういった分割の個数を与えると考えることができる。

この考え方は \(3\) 個以上の部分集合への分割に一般化できる。\(A\) を \(n\) 要素集合、\(k_{1}\), \(k_{2}\), \(\ldots\), \(k_{m}\) を和が \(n\) に等しい非負集合とする。このとき、次の条件を満たす \(A\) の部分集合の列 \((A_{1},\ A_{2},\ \ldots,\ A_{m})\) を \(A\) の \((k_{1}, k_{2}, \ldots, k_{m})\)-分割と呼ぶ:

全ての \(i\) に対して \(|A_{i}| = k_{i}\) が成り立つ。
\(A_{i} \cup A_{2} \cup \cdots \cup A_{m} = A\) が成り立つ。
全ての異なる \(i\), \(j\) に対して \(A_{i} \cap A_{j} = \varnothing\) が成り立つ。

\((k_{1}\, k_{2}\, \ldots\, k_{m})\)-分割の個数は部分集合則の導出と同様のアプローチで計算できる。具体的には次の通りである。\(n\) 要素集合 \(A\) の置換 \((a_{1}, a_{2}, \ldots, a_{n})\) が与えられたとき、先頭から \(k_{1}\) 要素を \(A_{1}\) の要素として、次の \(k_{2}\) 要素を \(A_{2}\) の要素とする。以下同様に最後の \(k_{m}\) 要素を \(A_{m}\) とするまで続ければ、\(A\) の置換から \(A\) の \((k_{1}\, k_{2}\, \ldots\, k_{m})\)-分割 \((A_{1},\ A_{2},\ \ldots,\ A_{m})\) が得られる。この写像は \(n!\) 個ある \(A\) の置換から \((k_{1}\, k_{2}\, \ldots\, k_{m})\)-分割への \(k_{1}! k_{2}! \cdots k_{m}!\) 対 \(1\) の写像なので、除算則を使えば次の部分集合分割則 (subset split rule) が得られる:

定義 15.6.1

\(k_{1} + k_{2} + \cdots + k_{m} = n\) を満たす \(n, k_{1}, \ldots, k_{m} \in \mathbb{N}\) に対して、多項係数 (multinomial coefficient) を次のように定義する:

\[ \binom{n}{k_{1},\, k_{2},\, \ldots,\, k_{m}} ::= \frac{n!}{k_{1}!\, k_{2}!\, \cdots\, k_{m}!} \]

規則 15.6.2[部分集合分割則 (subset split rule)]

\(n\) 要素集合の \((k_{1}, k_{2}, \ldots, k_{m})\)-分割の個数は次の式で表される:

\[ \binom{n}{k_{1},\, k_{2},\, \ldots,\, k_{m}} \]

15.6.2 bookkeeper 則

ちょうど \(k\) 個の \(1\) を含む長さ \(n\) のビット列の個数を与える系 15.5.2 を一般化すると、\(3\) 個以上の文字からなるアルファベットが並んだ長さ \(n\) の文字列の個数を計算する方法が得られる。例えば、\(\text{BOOKKEEPER}\) に含まれるアルファベット \(10\) 文字を並び替えて作れる列はいくつあるだろうか？

\(\text{BOOKKEEPER}\) は \(\text{B}\) を \(1\) 個、\(\text{O}\) を \(2\) 個、\(\text{K}\) を \(2\) 個、\(\text{E}\) を \(3\) 個、\(\text{P}\) を \(1\) 個、\(\text{R}\) を \(1\) 個含む。よって、\(\text{BOOKKEEPER}\) の置換全体の集合から \(\left\{ 1, 2, \ldots, 10 \right\}\) の \((1,2,2,3,1,1)\)-分割全体の集合への自然な全単射が存在する。具体的には、置換が移される分割に属する集合のそれぞれが対応する文字の位置を表す。

例えば、置換 \((\text{B}, \text{O}, \text{O}, \text{K}, \text{K}, \text{E}, \text{E}, \text{P}, \text{E}, \text{R})\) において、\(\text{B}\) は位置 \(1\) に、\(\text{O}\) は位置 \(2\), \(3\) に、\(\text{K}\) は位置 \(4\), \(5\) に、\(\text{E}\) は位置 \(6\), \(7\), \(9\) に、\(\text{P}\) は位置 \(8\) に、\(\text{R}\) は位置 \(10\) にある。よって、この置換は次の \((1,2,2,3,1,1)\)-分割に移される:

\[ ( \left\{ 1 \right\},\ \left\{ 2, 3 \right\},\ \left\{ 4, 5 \right\},\ \left\{ 6, 7, 9 \right\},\ \left\{ 8 \right\},\ \left\{ 10 \right\} ) \]

この全単射と部分集合分割則から、\(\text{BOOKKEEPER}\) の文字を並び替えて得られる文字列の個数を計算できる:

\[ \frac{\overbrace{10!}^{\text{全ての置換}}}{\underbrace{1!}_{B}\ \underbrace{2!}_{O}\ \underbrace{2!}_{K}\ \underbrace{3!}_{E}\ \underbrace{1!}_{P}\ \underbrace{1!}_{R}\ } \]

この例を一般化すると、数え上げに関する非常に有用な規則が得られる:

規則 15.6.3[bookkeeperブックキーパー則 (bookkeeper rule)]

\(l_{1}\), \(\ldots\), \(l_{m}\) を異なる要素とする。\(l_{1}\) を \(k_{1}\) 個、\(l_{2}\) を \(k_{2}\) 個、 \(\cdots\) 、\(l_{m}\) を \(k_{m}\) 個だけ含む列の個数は次の式で表される:

\[ \binom{k_{1} + k_{2} + \cdots + k_{m}}{k_{1},\ \ldots,\ k_{m}} \]

例えば、東西南北の方向にそれぞれ \(5\) マイルずつ走る計 \(20\) マイルのランニングを計画しているとする。道路が \(1\) マイル単位の格子状であるとき、ランニングのルートにはいくつの選択肢があるだろうか？

ランニングのルートから「東」を \(5\) 個、「西」を \(5\) 個、「南」を \(5\) 個、「北」を \(5\) 個含む長さ \(20\) の列への全単射が存在するので、bookkeeper 則から次の答えが得られる:

\[ \frac{20!}{(5!)^{4}} \]

用語について

将来、大勢の同僚の前で「部分集合分割則」や「bookkeeper 則」などの用語を使うと、ポカンとした顔で自分を見つめる聴衆に気が付くことになるだろう。この理由は彼らが馬鹿だからではなく、本書で使ってきた「bookkeeper 則」などの用語が著者らの作った独自のものだからである。しかし、規則自体は非常に有用で名前は憶えやすいので、芝居を打つことを勧める: 「知らないのか？あの bookkeeper 則を？おいおい、君たちの頭は空っぽだな！」

bookkeeper 則は「区別できないオブジェクトの置換の公式」と呼ばれることがある。\(n\) 要素集合の \(k\) 要素部分集合は \(k\)-組み合わせ (\(k\)-combination) とも呼ばれる。他にも「重複を許す組み合わせ」「重複を許す置換」「\(r\)-置換」「区別できないオブジェクトの置換」といった用語がある。しかし、本章で見てきた規則を使えば幅広い種類の組み合わせの問題が解けるので、こういった用語の理解・暗記は課さない。

15.6.3 二項定理

数え上げを使うと、代数における基礎的な定理の一つを証明できる。\(a + b\) のような二つの項の和の形をした式を二項式 (binomial) と呼ぶ。二項式 \(a + b\) を \(4\) 乗した \((a + b)^{4}\) を展開した式を考えよう。

和に対する積の分配律を繰り返し使って \((a + b)^{4}\) を完全に展開すると、次の等式が得られる:

\[ \begin{array}{cccccccccc} (a + b)^{4} &= & & aaaa & + &aaab & + & aaba & + & aabb \\ & & + & abaa & + &abab & + & abba & + & abbb \\ & & + & baaa & + &baab & + & baba & + & babb \\ & & + & bbaa & + &bbab & + & bbba & + & bbbb \end{array} \]

右辺には \(a\) と \(b\) からなる長さ \(4\) の列それぞれに対応する項がちょうど \(1\) 個あることに注目してほしい。ここから、右辺には \(2^{4}\) 個の項があると分かる。さらに、bookkeeper 則を使えば \(k\) 個の \(b\) と \(n - k\) 個の \(a\) を含む項の個数を求められる:

\[ \frac{n!}{k!\,(n-k)!} = \binom{n}{k} \]

つまり、\(k = 0,1,2,3,4\) に対して \(a^{n-k}b^{k}\) の係数は \(\displaystyle \binom{n}{k}\) である。\(n = 4\) だったから、これは次の等式を意味する:

\[ (a + b)^{4} = \binom{4}{0} \cdot a^{4} b^{0} + \binom{4}{1} \cdot a^{3} b^{1} + \binom{4}{2} \cdot a^{2} b^{2} + \binom{4}{3} \cdot a^{1} b^{3} + \binom{4}{4} \cdot a^{0} b^{4} \]

以上の議論を一般化すると次の定理を得る:

定理 15.6.3[二項定理 (binomial theorem)]

全ての \(n \in \mathbb{N}\) で次の等式が成り立つ:

\[ (a + b)^{n} = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k} \]

二項定理は \(\displaystyle \binom{n}{k}\) が二項係数 (binomial coefficient) と呼ばれる理由でもある。

ここまでの二項式に関する議論は多項式 (multinomial) にも自然に拡張できる。多項式とは \(3\) 個以上の項の和を言う。例えば、\((b + o + k + e + p + r)^{10}\) を展開した式における次の項の係数を求めたいとする:

\[ b o^{2}k^{2}e^{3}p r \]

展開した式の各項は \(10\) 個の変数の積であり、各変数は \(b\), \(o\), \(k\), \(e\), \(p\), \(r\) のいずれかである。よって、\(bo^{2}k^{2}e^{3}pr\) の係数は \(b\) を \(1\) 個、\(o\) を \(2\) 個、\(k\) を \(2\) 個、\(e\) を \(3\) 個、\(p\) を \(1\) 個、\(r\) を \(1\) 個だけ含む項の個数に等しい。これは \(\text{BOOKKEEPER}\) を並び変えて作れる文字列の個数そのものである:

\[ \binom{10}{1,\,2,\,2,\,3,\,1,\,1} = \frac{10!}{1!\;2!\;2!\;3!\;1!\;1!} \]

以上の議論を一般化すると次の定理を得る:

定理 15.6.5[多項定理 (multinomial theorem)]

全ての \(n \in \mathbb{N}\) で次の等式が成り立つ:

\[ (z_{1} + z_{2} + \cdots + z_{m})^{n} = \sum_{\substack{k_{1}, \ldots, k_{m} \in \mathbb{N} \\[2pt] k_{1} + \cdots + k_{m} = n}} \binom{n}{k_{1}, k_{2}, \ldots, k_{m}} z_{1}^{k_{1}} z_{2}^{k_{2}} \cdots z_{m}^{k_{m}} \]

ただ、この複雑な定理を記憶するよりは、この定理を導いた議論を思い出せるようにした方がいいだろう。