有名な「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個などと一般化されたら手も足も出なくなります。
この問題はもっと綺麗な方法で一般化して解くことはできないのでしょうか。

No.1 回答者： aiueo95240 回答日時： 2008/11/15 02:36

n個の異なるものをk個のグループに分割する総数は、第二種スターリング数S(n,k)=(1/k!)Σ[i=0,k] (-1)^i kCi (k-i)^nとなります。

アイデアとしては、
包除原理
計数子
二項変換の反転公式
漸化式
などがあります。

この回答への補足

ちょっと検索してみたんですが、はっきり言ってまったく分かりません・・・
（というか、どう見ても高校範囲で理解できるとは思えない）。
個人的に、もしかして漸化式が必要なのかなあ・・・とかは思っていたのですが。
とりあえず、高校範囲では無理、泥臭い方法で解け。
一般化なんて難しすぎてまず受験では出てこない。
ということでいいのでしょうか？

補足日時：2008/11/15 02:59