m個の球をn個の部屋に分けるとする(m>n)
ただしどの部屋にも必ず一つは球があるのを条件とする。
今、f(m,n)を、m個の球がn個の部屋に空部屋なく入っている通り数とする。
球は1からmまで番号が降ってあるものとする。
今、f(m+1,n)を表す漸化式を作る。
[1]箱に区別があるとき
(1)m+1番目の球を孤立させるとき
はじめにm+1番目の球を入れておくと
n×f(m,n-1)通り
(2)m+1番目の球を孤立させないとき
はじめに1～m番目までの球を空き部屋なく入れておくと
f(m,n)×n通り
以上より、
[2]箱のい区別がないとき
(1)m+1番目の球を孤立させるとき
はじめにm+1番目の球を入れておくと、
1×f(m,n-1)通り
(2)m+1番目の球を孤立させないとき
はじめに1～m番目までの球を相部屋なく入れておくと
f(m,n)×n通り
以上より、
最終更新：2012年10月03日 23:57
