Stirling number of the second kind

http://planetmath.org/encyclopedia/StirlingNumbersSecondKind.html

N個のものをK個の集合に分ける方法。素敵すぎる。やっぱり数学者はｶｺｲｲ。この式は離散数学への招待(isbn:4431708960)でよく使われている方法で求められる。S(n,n), S(n,1)の時は明らかに1個しか分ける方法がない。S(n,k)の時は、まずn個の物のうちどれか1個を抜いて考える。残りの物をk個の集合に分けるとS(n-1,k)個の分け方が存在する。そしたらそのうち1個に抜いた奴を追加してやる。追加する方法はk通りあるのでkS(n-1,k)。また、抜いた奴1個だけからなる集合を作って、残ったn-1個からk-1個の集合を作る。そうするとS(n,k)=kS(n-1,k)+S(n-1,k-1)となる。覚え方簡単。