Bell Numbers — Summary
The Bell numbers $B_n$ form an important sequence in combinatorics. They count the number of ways an $n$-element set can be divided into nonempty, disjoint subsets. In other words, $B_n$ gives the total number of possible partitions of a set, where the order of the subsets does not matter.
The sequence begins
$B_0=1,\quad B_1=1,\quad B_2=2,\quad B_3=5,\quad B_4=15,\quad B_5=52,\quad B_6=203,\ldots$
For example, the set ${a,b,c}$ has exactly five possible partitions, so $B_3=5$. Bell numbers also count the number of possible equivalence relations on a set containing $n$ elements.
Bell numbers are closely connected with the Stirling numbers of the second kind. If $S(n,k)$ denotes the number of ways to partition a set of $n$ elements into exactly $k$ nonempty subsets, then
$B_n=\sum_{k=0}^{n}S(n,k)$.
They also satisfy the recurrence relation
$B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_k$.
Their exponential generating function is
$\sum_{n=0}^{\infty}\frac{B_n}{n!}x^n=e^{e^x-1}$.
These formulas show the close relationship between Bell numbers, set partitions, Stirling numbers and generating functions. Bell numbers grow very rapidly as $n$ increases, and their asymptotic behaviour can also be described using the Lambert $W$ function.
The numbers are named after the mathematician Eric Temple Bell, who studied them during the 1930s, although the underlying combinatorial ideas appeared much earlier.
An interesting historical example comes from Japan. A traditional incense game associated with The Tale of Genji involves five groups and produces exactly $B_5=52$ possible patterns, corresponding to the 52 possible partitions of a five-element set.
Key takeaways
ARTICLE
The Bell numbers $B_n$ form an important sequence in combinatorics. They count the number of ways an $n$-element set can be divided into nonempty, disjoint subsets. In other words, $B_n$ gives the total number of possible partitions of a set, where the order of the subsets does not matter.
The sequence begins
$B_0=1,\quad B_1=1,\quad B_2=2,\quad B_3=5,\quad B_4=15,\quad B_5=52,\quad B_6=203,\ldots$
For example, the set ${a,b,c}$ has exactly five possible partitions, so $B_3=5$. Bell numbers also count the number of possible equivalence relations on a set containing $n$ elements.
Bell numbers are closely connected with the Stirling numbers of the second kind. If $S(n,k)$ denotes the number of ways to partition a set of $n$ elements into exactly $k$ nonempty subsets, then
$B_n=\sum_{k=0}^{n}S(n,k)$.
They also satisfy the recurrence relation
$B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_k$.
Their exponential generating function is
$\sum_{n=0}^{\infty}\frac{B_n}{n!}x^n=e^{e^x-1}$.
These formulas show the close relationship between Bell numbers, set partitions, Stirling numbers and generating functions. Bell numbers grow very rapidly as $n$ increases, and their asymptotic behaviour can also be described using the Lambert $W$ function.
The numbers are named after the mathematician Eric Temple Bell, who studied them during the 1930s, although the underlying combinatorial ideas appeared much earlier.
An interesting historical example comes from Japan. A traditional incense game associated with The Tale of Genji involves five groups and produces exactly $B_5=52$ possible patterns, corresponding to the 52 possible partitions of a five-element set.
Key takeaways
- Definition: $B_n$ is the number of partitions of an $n$-element set.
- First values: $1,1,2,5,15,52,203,877,4140,\ldots$
- Connection with Stirling numbers: $B_n=\sum_{k=0}^{n}S(n,k)$.
- Recurrence relation: $B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_k$.
- Generating function: $\sum_{n=0}^{\infty}\frac{B_n}{n!}x^n=e^{e^x-1}$.
- Area of mathematics: mainly combinatorics and discrete mathematics, with connections to probability, number theory and analytic combinatorics.
ARTICLE
┌────────────────────────────────┐
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘