部分集合の個数と部屋割り〜重複順列が効く 2 つの場面

5 個の要素をもつ集合の部分集合は 32 個。6 人を 3 つの部屋に入れる入れ方は 729 通り。

どちらも $2^5$ と $3^6$ で、同じ形の計算です。ものを 1 つずつ見て、行き先を独立に決める。この形が重複順列にあたります。

1 つずつ行き先を決める

$n$ 個のものがあり、それぞれに $k$ 通りの行き先があるとします。行き先どうしは干渉しません。

1 つ目に $k$ 通り、2 つ目にも $k$ 通り、と続くので、全体は $k$ を $n$ 回掛けた値になる。

$$k^n$$

これが重複順列の形です。$n$ が肩に乗る点が、${}_n{\mathrm{P}}_r$ や ${}_n{\mathrm{C}}_r$ と大きく違います。

部分集合の個数

要素が $n$ 個の集合について、部分集合がいくつあるかを数えます。

要素を 1 つずつ見て、「入れる」か「入れない」かを決める。どの要素についても 2 通りで、他の要素の判断に左右されません^[1]。

$$2^n$$

5 個なら $2^5=32$ 個。空集合とその集合自身も、部分集合として数に入ります。

大きさごとに数えても同じ

部分集合を、要素の個数で分類して足すこともできます。

$n$ 個から $r$ 個を選ぶのが ${}_n{\mathrm{C}}_r$ 通りなので、$r$ を 0 から $n$ まで動かして足す。

$${}_n{\mathrm{C}}_0+{}_n{\mathrm{C}}_1+\cdots +{}_n{\mathrm{C}}_n=2^n$$

$n=4$ なら $1+4+6+4+1=16$ で、$2^4$ と一致します^[1]。

同じものを 2 通りに数えたので、この等式が成り立ちます。二項定理で $a=b=1$ とした形にもなっている。

例：空集合を除く場合

「少なくとも 1 個を含む部分集合」なら、空集合を除きます。$2^n-1$ 個。

5 個の要素なら $32-1=31$ 個。「その集合自身を除く」なら、さらに 1 を引いて 30 個です。

問題文が真部分集合を求めているかどうかを確かめる。言葉の違いで 1 か 2 だけ変わります。

例：特定の要素を含む部分集合

$\{a,b,c,d,e\}$ の部分集合のうち、$a$ を必ず含むものを数えます。

$a$ は「入れる」で固定なので、残る 4 個について 2 通りずつ。$2^4=16$ 個です。

$a$ を含み $b$ を含まないものなら、2 個が固定されて $2^3=8$ 個。固定した要素のぶんだけ指数が下がる。

部屋割りは同じ形

$n$ 人を $k$ 個の部屋に入れる問題も、1 人ずつ行き先を決める形です。

人を 1 人ずつ見て、どの部屋に入るかを $k$ 通りから選ぶ。他の人の行き先には左右されません。

$$k^n$$

6 人を 3 部屋に入れるなら $3^6=729$ 通り。人が肩ではなく、部屋の数が底に来る点に気をつけます。

人と部屋のどちらが底か

底と肩をとり違えると、まったく違う値になります。$3^6=729$ と $6^3=216$ は別の数です。

判断の基準は、「1 つずつ行き先を決めるのはどちらか」。人が部屋を選ぶので、人の数が肩に乗る。

空室を認めない場合

「どの部屋にも 1 人以上」という条件が付くと、掛け算だけでは足りません。空室のある入れ方を引きます。

6 人を 3 部屋に空室なしで入れる場合。全体 $3^6=729$ から、ある 1 部屋が空になる $2^6=64$ 通りを 3 部屋ぶん引く。

2 部屋が空になる場合を引きすぎているので、$3\times 1=3$ を足し戻します。

$$729-3\times 64+3=729-192+3=540$$

540 通りです。

例：4 人を 3 部屋へ

小さい数で確かめます。全体 $3^4=81$ 通り。

1 部屋が空になるのが $2^4=16$ 通りで 3 部屋ぶんの 48。2 部屋が空になるのが 1 通りで 3 通りぶん。

$81-48+3=36$ 通りです。

部屋に番号がない場合は、部屋の入れ替え $3!=6$ 通りが重なるので割ります。番号があるかどうかを問題文で確かめる。

例：区別しないものを配る

同じあめ玉 6 個を 3 人に配る場合は、$3^6$ になりません。あめ玉に区別がないので、1 つずつ行き先を決める形にならない。

こちらは仕切りの方法で、${}_{6+2}{\mathrm{C}}_2=28$ 通り。配るものが区別できるかどうかで、まったく別の式になります。

例：写像の個数として読む

部屋割りは、$n$ 個の元から $k$ 個の元への写像の個数と同じです。行き先を 1 つずつ決めるので $k^n$ 個。

どの部屋にも 1 人以上、という条件は「全射」にあたります。1 人以下という条件なら「単射」で、${}_k{\mathrm{P}}_n$ 通り。

高校では写像という言葉を使わずに解きますが、同じ構造だと知っておくと見通しがよくなります。

例：旗を並べる

3 色の旗を 5 本立てます。同じ色を何本使ってもよく、立てる場所には順序があるとする。

1 本ずつ色を決めるので $3^5=243$ 通り。旗が肩、色が底です。

「3 色すべてを使う」なら空室なしと同じ形で、$243-3\times 2^5+3=243-96+3=150$ 通り。

例：試験の答案

正誤問題が 8 問あり、各問に丸かバツを書きます。答案の書き方は $2^8=256$ 通り。

「少なくとも 1 問は丸」なら $256-1=255$ 通り。部分集合の数え方とまったく同じ形です。

丸を付ける問題の集合を選ぶ、と読み替えれば部分集合そのものになる。

よくある誤り

配るものを 1 つずつ見て、行き先が独立に決まるか。ここが $k^n$ を使ってよい合図になります。

参考文献

^[1] が部分集合の個数と二項係数の和、^[2] が重複順列の位置づけ、^[3] が仕切りによる数え方、^[4] が空室なしの処理、^[5] が各国語での整理です。