Computing the n-th Bell number B_n

1. \(B_n\) is the number of partitions of a set with \(n\) elements;
2. \(B_{n+1}=\displaystyle{\sum_{k=0}^n}\binom{n}{k}B_k\), with \(B_0=1\);
3. \(B_n=\displaystyle\sum_{k=1}^n\frac{k^n}{k!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!}; \)
4. \(B_n=\displaystyle\frac{1}{e}\sum_{k=0}^\infty\frac{k^n}{k!}; \)
5. Via the Aitken table \(A_{i,j}\):

   \(\displaystyle A_{1,1}=1,\)
   \(\displaystyle A_{n,1}=A_{n-1,n-1}\), \(\quad n\gt 1,\)
   \(\displaystyle A_{n,k}=A_{n,k-1}+A_{n-1,k-1}, \quad 1\lt k\leq n\).

   Then \(B_n=A_{n,n},\quad 1\leq n\);

   \(A_{n,k}\) is the number of partitions of \(\{1,\ldots,n+1\}\) in which \(\{k+1\}\) is the singleton with the largest entry in the partition. (See references (2) and (3).)

6. \(B_n=\displaystyle{\sum_{k=1}^n}S_{n,k}\),
   where \(S_{n,k}, 1\le n, 1\le k\le n\) is the Stirling number of the second kind:
   \(S_{n,1}=1, n\ge 1\) and \(S_{n+1,k}=k\times S_{n,k} + S_{n,k-1}, \quad 2\leq k\leq n\).

1. OEIS: A000110
2. The largest singleton of set partitions, Yidong Sun, Xiaojuan Wu ( reference supplied by David Guichard)
3. Bell numbers (David Guichard)

Last modified 5th March 2023
Return to main page