Lesson 9

It is easy to see that \[B(n)=\sum_{k=0}^{n}S(n,k) \ .\] The number \(B(n)\) can also be expressed in terms of smaller Bell numbers. Element \(n\) is part of some subset with other elements. All these other elements form a set of size \(0 \leq k \leq n-1\). These \(k\) elements can be chosen in \(\binom{n-1}{k}\) ways. The remaining \(n-k-1\) elements can be partitioned in any of \(B(n-k-1)\) ways. Thus, \[B(n)=\sum_{k=0}^{n-1}\binom{n-1}{k}B(n-k-1) \ .\]