15.5 部分集合の数え上げ

\(n\) 要素集合に \(k\) 要素部分集合はいくつあるだろうか？ この質問は様々な形で姿を現す:

• 本棚にある \(100\) 冊の本から旅行に持っていく \(5\) 冊を選ぶ方法は何通りか？

• ブリッジでは \(52\) 枚のトランプ一式から \(13\) 枚の手札が配られる。何通りの手札が存在するか？

• ピザに追加できるトッピングを \(14\) 種類の中から \(5\) 種類だけ選べるとき、選び方は何通りか？

この質問は数学で余りにも頻繁に登場するので、その解答を表す特別な記法が用意されている:

\(\displaystyle \binom{n}{k}\) は「\(n\) chooseチューズ \(k\)」と読む。この記法を使えば、上記の質問には簡単に答えられる:

• \(100\) 冊の本から \(5\) 冊を選ぶ方法は \(\displaystyle \binom{100}{5}\) 通りある。

• ブリッジの手札は \(\displaystyle \binom{52}{13}\) 通りある。

• \(14\) 種類のトッピングから \(5\) 種類を選べるとき、全部で \(\displaystyle \binom{14}{5}\) 種類の異なるピザを注文できる。

15.5.1 部分集合則

\(\displaystyle \binom{n}{k}\) を表す単純な式は除算則を使って導出できる。\(n\) 要素集合 \(\left\{ a_{1}, \ldots, a_{n} \right\}\) の置換を先頭 \(k\) 要素からなる部分集合に対応付ける写像を考える。例えば、置換 \((a_{1}, a_{2}, \ldots, a_{n})\) は部分集合 \(\left\{ a_{1}, a_{2}, \ldots, a_{k} \right\}\) に移される。

先頭 \(k\) 要素に \(a_{1}\), \(\ldots\), \(a_{k}\) を任意の順序で含む置換は、この写像によって同じ部分集合 \(\left\{ a_{1}, \ldots, a_{k} \right\}\) に移される。さらに、この部分集合に移される置換は必ず先頭要素に \(a_{1}\), \(\ldots\), \(a_{k}\) を持つ。そのような置換の先頭 \(k\) 要素の並べ方は \(k!\) 通り存在し、残りの \(n - k\) 要素の並べ方は \((n - k)!\) 通り存在する。よって乗算則より、特定の \(k\) 要素部分集合に移される置換はちょうど \(k!(n - k)!\) 個ある。言い換えれば、置換を \(k\) 要素部分集合に移す写像は \(k!(n-k)!\) 対 \(1\) の写像である。

一方で \(n\) 要素集合の置換が \(n!\) 個あることは以前に見た。よって除算則から次の等式が分かる:

これで次の規則が証明できた:

この等式は \(k = 0\) の場合でも成り立つことに注意してほしい: \(0\) 要素部分集合は空集合しか存在せず、\(n!/(0!n!) = 1\) が成り立つ。この計算では、\(0!\) が \(0\) 個の項の積を表し、その値は慣習的¹に \(1\) と定義される事実を利用している。

15.5.2 ビット列

ちょうど \(k\) 個の \(1\) を含む長さ \(n\) のビット列はいくつあるだろうか？ \(n\) 要素集合の部分集合全体の集合から長さ \(n\) のビット列全体の集合への全単射の存在は以前に見た。この全単射で対応付く \(\left\{ x_{1}, x_{2}, \ldots, x_{8} \right\}\) の部分集合とビット列の例を次に示す:

ここから分かるように、\(3\) 要素部分集合にはちょうど \(3\) 個の \(1\) を含む長さ \(8\) のビット列が対応する。一般に、\(k\) 要素部分集合に対応する長さ \(n\) のビット列は \(k\) 個の \(1\) を含む。よって全単射則より次の系が分かる:

また、補題 15.1.1 で示したドーナツの選び方とビット列の関係からは次の系が分かる: