Bell Numbers

We use a direct combinatorial (bijective counting) argument, together with the additivity of counting over a partition of the sample space.

Setup. Fix $n \ge 0$ and consider the set $[n+1] = \{1, 2, \dots, n, n+1\}$. We count the partitions of $[n+1]$ by conditioning on the block that contains the specific element $n+1$; call this block $B(n+1)$.

Step 1: classify by the size of the companion set. Since $B(n+1) \subseteq [n+1]$ and $n+1 \in B(n+1)$, we may write

where $C \subseteq \{1, 2, \dots, n\}$ is the (possibly empty) set of elements from $[n]$ that share a block with $n+1$. Let $k = n - |C|$, i.e. $|C| = n-k$, so $k$ ranges over $\{0, 1, \dots, n\}$ and represents the number of elements of $[n]$ not in the block of $n+1$. The set of all partitions of $[n+1]$ is the disjoint union, over $k = 0, 1, \dots, n$, of the set of partitions in which exactly $k$ elements of $[n]$ lie outside the block of $n+1$. This is a genuine partition of the sample space (each partition of $[n+1]$ has a uniquely determined companion set $C$, hence a uniquely determined $k$), so by additivity of counting,

Step 2: count each term by a two-stage choice. Fix $k \in \{0, \dots, n\}$. A partition of $[n+1]$ of this type is uniquely specified by two independent pieces of data: 1. The set $C \subseteq [n]$ with $|C| = n-k$ that, together with $n+1$, forms the block $B(n+1) = \{n+1\}\cup C$. There are $\binom{n}{n-k} = \binom{n}{k}$ choices for $C$ (choosing which $n-k$ of the $n$ elements of $[n]$ join $n+1$; equivalently, choosing the complementary set of $k$ elements that stay outside). 2. A partition of the remaining $k$ elements — those in $[n] \setminus C$, a set of size $k$ — into blocks. Since blocks are determined purely by which elements group together, the number of ways to partition any $k$-element set is $B_k$, independent of which $k$ elements they are (partitions of $[n]\setminus C$ are in bijection with partitions of $[k]$ via any fixed bijection $[n]\setminus C \to [k]$, since the definition of a partition depends only on the equality/inequality structure, not on the labels themselves). These two choices are independent and jointly determine the full partition of $[n+1]$: the block containing $n+1$ is $\{n+1\}\cup C$, and the remaining blocks are exactly the blocks of the chosen partition of $[n]\setminus C$. Conversely, every partition of $[n+1]$ with companion-set size $n-k$ arises this way, and distinct choices of $(C, \text{partition of } [n]\setminus C)$ give distinct partitions of $[n+1]$ (they differ either in the block containing $n+1$, or, if not, in some other block). Hence the number of partitions of $[n+1]$ with exactly $k$ elements outside $B(n+1)$ equals

Step 3: sum. Combining Steps 1 and 2,

as claimed. $\blacksquare$

We give a proof via the exponential formula for labeled structures, derived here from first principles using the Stirling-number decomposition, so the argument is self-contained given only the EGF product rule (the EGF of a sequence counting "labeled structure on a set, decomposed into an ordered sequence of substructures on a set partition" equals the appropriate composition/exponential of building-block EGFs — we re-derive the specific instance needed rather than citing the formula as a black box).

Step 1: EGF of "exactly one nonempty block." A single nonempty block on a labeled set of size $m \ge 1$ can be realized in exactly $1$ way (there is only one way to make a given set into a single block). So the sequence "$1$ if $m\ge1$, else $0$" has EGF

Step 2: EGF of "a set partition into exactly $k$ unlabeled nonempty blocks", summed with a marker for $k$. We first handle ordered partitions into exactly $k$ blocks (an ordered $k$-tuple of disjoint nonempty subsets covering $[n]$), and then divide by $k!$ to un-order them. Fix $k \ge 1$. The number of ways to partition $[n]$ into an ordered sequence of $k$ nonempty, disjoint blocks $(A_1, \ldots, A_k)$ whose union is $[n]$ is exactly $k! \, S(n,k)$, since each unordered partition into $k$ blocks gives rise to $k!$ ordered versions and no two distinct unordered partitions or two distinct orderings coincide. The EGF product rule states: if $a_n$ is the number of ways to linearly order a labeled structure on $[n]$ as a sequence of $k$ "pieces" built from a class with EGF $f(x)$ (each piece a nonempty labeled block, here with per-block EGF $f(x) = e^x-1$ from Step 1), assembled by first partitioning $[n]$ into an ordered sequence of $k$ blocks and then decorating each block independently, then the EGF of $(a_n)_n$ is $f(x)^k$. This is because multiplying EGFs corresponds exactly to the "choose a subset for block 1, a subset for block 2 among what remains, etc." labeled product construction: for each $n$,

which for our case (each block simply "is" a set, weight $1$ if nonempty) gives precisely the count of ordered partitions of $[n]$ into $k$ nonempty labeled blocks. Concretely here, since each block's generating function is $e^x - 1$,

which is a standard and directly checkable identity: expanding $(e^x-1)^k$ via inclusion–exclusion on which of $k$ "slots" a given element may avoid recovers the standard formula

and one verifies directly that $[x^n]\,n!\,(e^x-1)^k$ equals $k!$ times this expression, by expanding $(e^x - 1)^k = \sum_{j=0}^k \binom{k}{j}(-1)^{k-j} e^{jx}$ and reading off coefficients: $[x^n] n!\, e^{jx} = j^n$, so

the last equality being the (already-established, prerequisite) explicit formula for Stirling numbers of the second kind.

Step 3: unlabel the blocks and sum over $k$. To count unordered partitions into exactly $k$ blocks, divide by $k!$ (the number of orderings of $k$ distinguishable blocks — valid since all $k$ blocks are automatically distinct as sets, being disjoint and nonempty, so no overcounting from repeated blocks occurs). Hence the EGF of $S(n,k)$ (as a sequence in $n$, for fixed $k$) is

Summing over all $k \ge 0$ (with the $k=0$ term contributing only at $n=0$, matching $S(0,0)=1$) gives the EGF of $B_n = \sum_k S(n,k)$:

where the last equality is just the Taylor series of the exponential function evaluated at $e^x - 1$, valid for all real (indeed all complex) $x$ since $e^y = \sum_k y^k/k!$ converges everywhere. Convergence of the outer sum over $k$ for each fixed $x$ follows because $e^x - 1$ is a fixed real number once $x$ is fixed, and $\sum_k y^k/k!$ converges absolutely for every real $y$.

Step 4: radius of convergence of $B(x)$ itself. Since $e^{e^x-1}$ is an entire function (composition of entire functions), its Taylor series $\sum_n B_n x^n/n!$ converges for all $x \in \mathbb{C}$; in particular $B(x)$ has infinite radius of convergence, so the formal manipulations above are also valid as honest analytic identities. $\blacksquare$

We prove by strong induction on $n$ the joint statement:

This refined statement — tracking every entry in row $n$, not just the endpoints — is what makes the induction go through cleanly (a direct induction on just the endpoints would not have enough information to advance a row).

Base case $n=1$. Row $1$ has the single entry $a_{1,1}=1$. We check $P(1)$: $a_{1,1}$ should equal $B_0 = 1$ ✓, and the sum formula with $k=1$ gives $\sum_{j=0}^0 \binom{0}{0}B_{1-1+0} = B_0 = 1$ ✓.

Inductive step. Suppose $P(n)$ holds for some $n \ge 1$; we show $P(n+1)$. First entry of row $n+1$. By definition, $a_{n+1,1} = a_{n,n}$. By the inductive hypothesis $P(n)$ applied at $k=n$,

where the last equality is precisely the Bell recurrence proved above (with $n$ there playing the role of $n-1$ here, i.e. $B_{(n-1)+1} = \sum_{j=0}^{n-1}\binom{n-1}{j}B_j$). Hence $a_{n+1,1} = B_n = B_{(n+1)-1}$, confirming the first half of $P(n+1)$. General entry of row $n+1$, by induction on $k$ within the row. We show, for $1\le k \le n+1$,

by induction on $k$. The case $k=1$ is exactly the first-entry computation just done. Suppose the formula holds for row $n+1$ at position $k-1$ (where $2 \le k \le n+1$), i.e.

By the defining recurrence of the triangle,

The second summand, by the outer inductive hypothesis $P(n)$ at position $k-1$ (valid since $k-1 \le n$), is

So

Reindex the first sum by $j = i+1$ (running $j=1,\dots,k-1$) and the second by $j=i$ (running $j=0,\dots,k-2$):

Combining the two sums termwise using Pascal's rule $\binom{k-2}{j-1}+\binom{k-2}{j} = \binom{k-1}{j}$ for the overlapping range $j=1,\dots,k-2$, and noting the $j=0$ term appears only in the second sum (coefficient $\binom{k-2}{0}=1=\binom{k-1}{0}$) and the $j=k-1$ term appears only in the first sum (coefficient $\binom{k-2}{k-2}=1=\binom{k-1}{k-1}$), we get

exactly the claimed formula for row $n+1$, position $k$. This completes the induction on $k$, and hence establishes the full statement $P(n+1)$.

Extracting the endpoint claim. Setting $k=n+1$ in the just-proved row formula for $P(n+1)$:

again by the Bell recurrence. This confirms the last entry of row $n+1$ is $B_{n+1}$, matching the theorem statement (shifted by one index from $P$'s bookkeeping, which used $B_{n-1}$ for the first entry of row $n$ — here $a_{n+1,n+1}=B_{n+1}$, consistent with "last entry of row $m$ is $B_m$" at $m=n+1$). By the principle of strong (here, ordinary, nested) induction, $P(n)$ holds for all $n \ge 1$, and the two extracted facts $a_{n,1}=B_{n-1}$, $a_{n,n}=B_n$ hold for all $n\ge1$. $\blacksquare$