場所占めの問題

質問

ｎ個のものをｒ個の箱に入れるときの場合の数
問1、ただし、物も箱も区別し、空の箱はないものとする
問2、ただし、物も箱も区別せず、空の箱はあってもよいものとする
問1はｒのｎ乗-（空の場合）ならできるのですが、それなら一般化されないので別の方法がないかと迷い、問2はｎ+ｒ－1Ｃｒ-1/ｒの階乗　ではないし泥沼にはまっています。誰か教えてください。

回答No.1

kony0 · ベストアンサー

一般式は難しいですね。せめて漸化式でも。

問１は
http://oshiete1.goo.ne.jp/kotaeru.php3?q=1760374
とまったく同じ問題ですね。

問２は・・・
求める場合の数をg(n,r)とすると
g(n,r)=Σ(k=0～[n/r])g(n-kr,r-1)
g(n,1)=1(n≧0), 0(n＜0)
で求められると思います。（いま即興で作ったので試してないですが^^;）

上記漸化式の考え方は、
r個の箱のうち、いちばん物が入っていない箱にk個入っている状況を考えます。
ということで、まずすべての箱にk個ずつのものを入れます。
残りのn-kr個の物を、r-1個の箱に入れることを考えています。