Total Number of Set Partitions

Theorem

Let $S$ be a finite set of cardinality $n$.

Then the number of different partitions of $S$ is $B_n$, where $B_n$ is the $n$th Bell number.

Proof

The number of different partitions of $S$ is defined as $B_n$.

From Bell Number as Summation over Lower Index of Stirling Numbers of the Second Kind:

$B_n = \ds \sum_{k \mathop = 0}^n {n \brace k}$

where $\ds {n \brace k}$ denotes a Stirling number of the second kind.

From Number of Set Partitions by Number of Components, $\ds {n \brace k}$ is the number of partitions of $S$ into $k$ components.

Hence the result.

$\blacksquare$

Example: $\card S = 2$

Let $S$ be a set whose cardinality is $2$.

Then the number of partitions of $S$ is $2$.

Example: $\card S = 3$

Let $S$ be a set whose cardinality is $3$.

Then the number of partitions of $S$ is $5$.

Example: $\card S = 4$

Let $S$ be a set whose cardinality is $4$.

Then the number of partitions of $S$ is $15$.