有名な「n人を空部屋なく3部屋に分けろ」問題。じゃあ4部屋以上のときは？
受験直前の知識整理をしていて思ったことです。
「n人を区別のない3部屋にわける方法は何通りあるか。ただし1人もいない部屋があってはならない」
・・・という問題は受験数学を勉強した人は多分皆解いたことがあると思います。
プロセスとしては、区別されるｘ個の部屋のうちy個(x > y)の部屋のみが
空となる場合の数をM(x,y)として、
（分かりにくいですが、あとの議論のためにわざと関数的に書きました）
2部屋だけが空となる場合の数を求める
→ M(3,2) = 3
1部屋だけが空となる場合の数を求める
→ M(3,1) = C[3,2]*M(2,0) = 3*(2^n - M(2,1)) = 3*(2^n - 2)
求める場合の数は
→ M(3,0) = 3^n - M(3,2) - M(3,1) = 3^n - 3*(2^n) +3
部屋は区別されないので3!で割る
・・・ところでこれ、4部屋以上になった場合はどうなるのでしょうか。
たとえば4部屋の場合、以下は自分が考えた解答ですが
（あってるかどうか分かりませんが、最終的にn=4でちゃんと1になるので大丈夫なはず・・・）
M(4,3) = 4
M(4,2) = C[4,2]*M(2,0) = 6*(2^n - 2) ←（M(2,0)は上記から）
M(4,1) = C[4,3]*M(3,0) = 4*(3^n - 3*(2^n) +3) ←（M(3,0)は上記から）
M(4,0) = 4^n - M(4,3) - M(4,2) - M(4,1)
= 4^n - 4*(3^n) + 6*(2^n) - 4
部屋は区別されないので4!で割る
しかしこれ、合っているとしてもものすごくやり方が泥臭い気がする上に、
部屋の数がm個などと一般化されたら手も足も出なくなります。
この問題はもっと綺麗な方法で一般化して解くことはできないのでしょうか。
