数学A / 場合の数

部屋割り(重複順列と空室の条件)

★★ 標準重複順列

問題

5人を、区別できる3つの部屋 A, B, C に入れる。

(1) 空室があってもよいとき、入れ方は何通りか。

(2) どの部屋にも少なくとも1人が入るとき、入れ方は何通りか。

ヒントを見る

(1)各人が独立に3部屋から選ぶ(重複順列)。(2)『どの部屋も空でない』は直接数えにくい — 全体から『少なくとも1部屋が空』を引く(空く部屋の選び方で足し引き=包除)。

解答・解説

(1)は「各人が3部屋から1つ選ぶ」重複順列で、 $3^{5}$ とすぐ出る。

(2)の「空室なし」は正面から数えると場合が多くて大変だ。そこで裏返して、全体から「空き部屋ができてしまう」場合を引く。

このとき、2部屋が空く場合を引き過ぎてしまうので、あとで足し戻す。この「引く→引き過ぎを足し戻す」がポイントだ。

⓪ 発想 — どう考え始めるか。 (1)は「各人が3部屋から1つ選ぶ」だけ。5人が独立に選ぶから $3^{5} = 243$ 通り(重複順列)。

(2)の「空室なし」は、正面から数えると場合が多くて大変だ。そこで裏返す。全体から「空き部屋ができる」場合を引く。

ただし「A が空く」と「B が空く」を単純に引くと、2部屋空く場合を引き過ぎる。あとで足し戻す。この「引く → 引き過ぎを足し戻す」が肝である。

公式重複順列:各人が独立に

m

通り → 全体は

m^{n}

通り

(1) 5人それぞれが、3つの部屋から自由に1つ選ぶ。各人3通りなので、かけ合わせて

$3^{5} = 243 (通り)$

(2) 「どの部屋にも1人以上」を最初から数えるのは大変なので、裏返して数える。全体243通りから、「空き部屋ができる」入れ方を引く。

まず「特定の1部屋を使わない(残り2部屋に全員入れる)」入れ方は $2^{5} = 32$ 通り。空にする部屋の選び方が $_{3} C_{1} = 3$ 通りあるので、いったん $3 \times 32 = 96$ を引く。

でもこれでは、「2部屋が同時に空く(全員が1部屋に集まる)」場合を2回引いてしまっている。この場合は $1^{5} = 1$ 通りで、空にする2部屋の選び方が $_{3} C_{2} = 3$ 通り。引き過ぎた分を足し戻す。

$3^{5} -_{3} C_{1} \cdot 2^{5} +_{3} C_{2} \cdot 1^{5} = 243 - 96 + 3 = 150 (通り)$

まとめ:「引く→引き過ぎを足し戻す」という流れは、3つの集合の個数定理とまったく同じだ。数える対象が「倍数」から「部屋割り」に変わっただけで、道具は同じだ。

発展 — 一歩先へ。 「どの部屋にも1人以上」は、数学の言葉では「5人から3部屋への割り当てで、全部屋が使われる」対応の個数だ。この型の数は、部屋数が増えると包除原理の一般形(足す・引くを交互に繰り返す)で数える。

包除ルートと内訳ルートの答えの一致は、強力な検算になる。数え上げでは「別の道で同じ答え」がいちばんの安心材料だ。

答

(1) 243通り (2) 150通り

(2)は、人数の内訳で場合分けして直接数えることもできる。空室なしで5人を3部屋に入れる内訳は、 $(3, 1, 1)$ 型と $(2, 2, 1)$ 型の2つしかない。

$(3, 1, 1)$ 型: 3人組になる人を選び( $_{5} C_{3} = 10$ )、その組の部屋を選び( $3$ 通り)、残り2人を残り2部屋へ( $2!$ )。 $10 \times 3 \times 2 = 60$ 通り。

$(2, 2, 1)$ 型: 2人・2人・1人に分ける方法は $\frac{_{5} C _{2} \times _{3} C _{2}}{2} = 15$ 通り(同じ人数の2組の入れ替えで割る)。できた3つの組を3部屋へ割り当てて $3!$ 。 $15 \times 6 = 90$ 通り。

合わせて $60 + 90 = 150$ 通り。包除ルートと一致する。

ちなみに定番の誤答「先に1人ずつ配ってから残りを自由に」( $5 \times 4 \times 3 \times 3^{2} = 540$ )は、同じ入れ方を何度も数えてしまう。直接ルートで内訳を固定すると、その重複が起きない理由も見えてくる。