information:extraction, linguistic:voice_change
Summation formulas

The Bell numbers satisfy a recurrence relation involving binomial coefficients:

It can be explained by observing that, from an arbitrary partition of n + 1 items, removing the set containing the first item leaves a partition of a smaller set of k items for some number k that may range from 0 to n. There are (n k) {\displaystyle {\tbinom {n}{k}}} choices for the k items that remain after one set is removed, and B choices of how to partition them.

A different summation formula represents each Bell number as a sum of Stirling numbers of the second kind

The Stirling number { n k } {\displaystyle \left\{{n \atop k}\right\}} is the number of ways to partition a set of cardinality n into exactly k nonempty subsets. Thus, in the equation relating the Bell numbers to the Stirling numbers, each partition counted on the left hand side of the equation is counted in exactly one of the terms of the sum on the right hand side, the one for which k is the number of sets in the partition.

Spivey 2008 has given a formula that combines both of these summations:

Applying Pascal's inversion formula to the recurrence relation, we obtain

B n = ∑ k = 0 n (n k) (− 1) n − k B k + 1, {\displaystyle B_{n}=\sum _{k=0}^{n}{\binom {n}{k}}(-1)^{n-k}B_{k+1},}

which can be generalized in this manner:

∑ j = 0 n (n j) B k + j = ∑ i = 0 k (k i) (− 1) k − i B n + i + 1. {\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}B_{k+j}=\sum _{i=0}^{k}{\binom {k}{i}}(-1)^{k-i}B_{n+i+1}.}

Other finite sum formulas using Stirling numbers of the first kind include

∑ j = 0 n (n j) a j b n − j B j = ∑ i = 0 k (− 1) k − i ∑ j = 0 n (n j) a j (b − a k) n − j B j + i, {\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}a^{j}b^{n-j}B_{j}=\sum _{i=0}^{k}\left(-1)^{k-i}\sum _{j=0}^{n}{\binom {n}{j}}a^{j}(b-ak)^{n-j}B_{j+i},}

which simplifies down with k = 1 {\displaystyle k=1} to

∑ j = 0 n (n j) a j b n − j B j = ∑ j = 0 n (n j) a j (b − a) n − j B j + 1 {\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}a^{j}b^{n-j}B_{j}=\sum _{j=0}^{n}{\binom {n}{j}}a^{j}(b-a)^{n-j}B_{j+1}}

and with a = 1 {\displaystyle a=1}, b = k {\displaystyle b=k} to

∑ j = 0 n (n j) B j k n − j = ∑ i = 0 k B n + i (− 1) k − i {\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}B_{j}k^{n-j}=\sum _{i=0}^{k}\leftB_{n+i}(-1)^{k-i}} which can be seen as the inversion formula for Stirling numbers applied to Spivey’s formula.