部屋割り（部屋に区別が無い場合）の練習問題（全4問・解答つき）

1. 2S1 は「区別する2個のボールを、区別しない1個の箱に最低1個は配る場合の数」である。これは、2個のボールを1つの箱にしまう 1 通り。

   

2. 2S2 は「区別する2個のボールを、区別しない2個の箱に最低1個は配る場合の数」 である。これは、2個のボールを2つの箱に1つずつしまう 1 通り。

   

3. 3S1 は「区別する3個のボールを、区別しない1個の箱に最低1個は配る場合の数」 である。これは、3個のボールを1つの箱にしまう 1 通り。

   

4. 3S2 は「区別する3個のボールを、区別しない2個の箱に最低1個は配る場合の数」 である。ボールを配るとき、ボールが1個の箱と2個の箱ができるが、どのボールが1個で箱に入るのかを考え、 3C1=3 通り。

   

まず、部屋を区別してから考える。求めるものは 9S3 である。

まず、3つの部屋を区別して考えていくため、部屋に a,b,c と名前を付ける。 空の部屋があってもよいとした場合、各部屋への人の泊まり方は、各人に対して部屋の選び方が3通りずつあるので、 3⁹ 通り。

このうち、空にする部屋を1つ決めて、残りの2部屋に9人を自由に泊めると

3C1・2⁹ 通り

となるが、この数え方では2部屋とも空になる場合を2回ずつ数えている。 2部屋が空部屋になるのは

3C2・1⁹ 通り

であるから、これを1回分引いて、1部屋以上の部屋が空部屋になるのは 3C1・2⁹- 3C2・1⁹ 通りである。 これは、はじめのボールと箱のモデルで使った包含と排除の原理 (3集合版)と同じ数え方である。

よって、空部屋が無いような人の泊まり方は

3⁹-( 3C1・2⁹- 3C2・1⁹) = 3⁹-3×2⁹+3=18150

より、 18150 通り

本来部屋は区別しないので、 3! で割って

(3⁹-3×2⁹+3)/3!=3025 通り

↑ 9S3

1. nSr すなわち「区別する n 個のボールを、区別しない r 個の箱に最低1個は配る場合の数」は、次の2つの場合に分けることができる。

   (i) 特定のボールが1つだけで入る箱がある

   (ii) 特定のボールが1つだけで入る箱がない

   (i)については、まず特定のボールを1つの箱に入れておいて、残り n-1 個のボールを残りの r-1 個の箱にしまえばよいから

   n-1Sr-1 通り

   

   (ii)については、まず特定のボール以外の n-1 個のボールを r 個の箱にしまっておいて、最後に特定のボールをすでに他のボールが 入っている r 個の箱のどれかにしまえばよいから

   n-1Sr×r 通り

   

   よって

   nSr= n-1Sr-1+r× n-1Sr

   が成り立つ。

2. 5S3= 4S2+3 4S3 = ( 3S1+2 3S2)+3( 3S2+3 3S3) = 3S1+9 3S3+5 3S2 = 3S1+9 3S3+5( 2S1+2 2S2) = 1+9+5(1+2・1)=25

部屋割り(部屋に区別が無い場合)の解答より、

空部屋が無いような人の泊まり方は

3025 通り

↑ 9S3

だった。

空部屋の数で分けると、ちょうど2部屋の場合、ちょうど1部屋の場合、0部屋の場合の3つになる。 0部屋の場合が上の 3025 通りなので、残りの2つを数える。

2部屋が空になるのは、部屋を区別した場合には、9人全員が a,b,c のどれか1部屋に泊まる3通りである。 この3通りは、部屋の区別をなくすとすべて同じ泊まり方になるので、3で割って

3/3=1 通り

1部屋が空になるのは、まず空にする部屋の選び方が 3C1 通りあり、残りの2部屋にはどちらにも1人以上泊まるので room(9,2)=2⁹-2=510 通りである。 これは、2部屋への泊まり方 2⁹ 通りから、9人全員が同じ部屋に泊まる2通りを除いた数である。 よって部屋を区別した場合には 3C1(2⁹-2)=1530 通りあり、今度は空の部屋1つと、泊まっている人の違う2部屋とで3つとも別物だから、部屋の区別をなくすには 3! で割ればよいので

3C1(2⁹-2)3!=255 通り

よって

1+255+3025=3281 通り

↑ 9S1+ 9S2+ 9S3

この例題からわかるように、空の部屋(箱)があってもよい場合の人(ボール)の分け方(配り方)は、 nSr の和となる。 ボールと箱のモデルでまとめると、次のようになる。