部屋割り（部屋に区別が無い場合）の練習問題（全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部屋以上の部屋が空部屋になるのは

3C1・2⁹ 通り

2部屋が空部屋になるのは

3C2・1⁹ 通り

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

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

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

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

↑ 9S3

1. nSr すなわち「区別する n 個のボールを，区別しない r 個の箱に最低1個は配る場合の数」は，

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

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

3025 通り

↑ 9S3

だった．

2部屋が空になるのは，部屋を区別した場合には3通りあるが，部屋の区別をなくすには3で割ればよいので

3/3=1 通り

1部屋が空になるのは，部屋を区別した場合には 3C1(2⁹−2) 通りあるが，部屋の区別をなくすには 3! で割ればよいので

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

よって

1+255+3025=3281 通り

↑ 9S1+ 9S2+ 9S3

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