ベル数の漸化式

ベル数\(B\left(n\right)\)は区別の出来る\(n\)個の玉を箱に分ける方法の数である。
\(n+1\)個の区別できるもの\(\left\{ a_{0},a_{1},\cdots,a_{n}\right\} \)を\(a_{0}\)を含むものと含まないもので別に考える。
\(a_{0}\)を含む箱に\(k+1\)個含まれているとき、この選び方は\(C\left(n,k\right)\)通りある。
このとき、残りの\(n-k\)個を箱に分ける方法は\(B\left(n-k\right)\)通りある。
これより、\(a_{0}\)を含む箱に\(k+1\)個含まれているときは\(C\left(n,k\right)B\left(n-k\right)\)通りの箱の分けかたがあるので、\(k\)について0から\(n\)まで和をとれば\(B\left(n+1\right)\)となる。
従って、
\begin{align*} B\left(n+1\right) & =\sum_{k=0}^{n}C\left(n,k\right)B\left(n-k\right)\\ & =\sum_{k=0}^{n}C\left(n,n-k\right)B\left(n-k\right)\\ & =\sum_{k=0}^{n}C\left(n,k\right)B\left(k\right) \end{align*} となる。