部分集合 計算ツールとは?
部分集合とは、ある集合から選び出した要素の組み合わせのことで、空集合や元の集合そのものも部分集合に含まれます。このツールは、組み合わせ論でよく問われる2つの疑問に答えます。1つは「n個の要素を持つ集合には全部でいくつの部分集合があるのか」、もう1つは「そのうち、ちょうどk個の要素を含む部分集合はいくつあるのか」です。集合論・確率・離散数学を学ぶ学生はもちろん、起こりうる組み合わせの数を数えたいすべての方に役立ちます。
使い方
まず、集合のサイズn(異なる要素の個数)を入力します。すると、部分集合の総数(\(2^n\)に等しい)と、空集合を除いた部分集合の数(\(2^n - 1\))がすぐに表示されます。さらにサイズkを入力すれば、ちょうどk個の要素を含む部分集合の数を、二項係数 \(C(n, k)\) を用いて求められます。総数だけ知りたい場合は、kを空欄のままにしておけば構いません。
公式のしくみ
集合の各要素は、部分集合に「含める」か「含めない」かのどちらかを独立に選べます。つまり要素1つあたり2通りの選択肢があるということです。要素がn個あれば、その総数は次のようになります。
$$\text{部分集合の総数} = 2 \times 2 \times \dots \times 2 = 2^n$$一方、サイズkに固定した部分集合の数を数えるには、組み合わせの公式を使います。
$$\binom{n}{k} = \frac{n!}{k!\,(n - k)!}$$これは順序を考えずにk個の要素を選ぶ方法の数です。kを0からnまで動かして\(C(n, k)\)をすべて足し合わせると、ちょうど\(2^n\)に戻ります。
計算例
たとえば n = 5 の場合を考えてみましょう。部分集合の総数は \(2^5 = 32\)、空集合を除いた部分集合の数は 31 です。要素2個の部分集合の数は次のようになります。
$$\binom{5}{2} = \frac{5!}{2! \cdot 3!} = \frac{120}{2 \cdot 6} = 10$$つまり、5個の要素からなる集合からは、ちょうど10通りのペアを作れるということです。
よくある質問
総数には空集合も含まれますか? はい。\(2^n\)という数には、空集合と元の集合そのものの両方が含まれます。空集合を除いた部分集合の数を求めるには1を引き、真の(元の集合自身を除く)空でない部分集合を求めるには2を引いてください。
kがnより大きい場合はどうなりますか? そのような部分集合は存在しないため、\(k > n\) または \(k < 0\) のときは \(C(n, k) = 0\) になります。
なぜ上限が170前後なのですか? \(2^n\)や階乗は非常に速く増大するため、おおよそ n = 170 を超えると、その値が標準的な浮動小数点数で表現できる範囲を超えてしまうからです。
